Sequence list and linked list

1. The linear table

The linear table (linear list) yes n A finite sequence of data elements with the same characteristics . Linear table is a kind of widely used in practice
Data structure used , Common linear tables ： The order sheet 、 Linked list 、 Stack 、 queue 、 character string ...

A linear table is logically a linear structure , That is, a continuous straight line . But it is not necessarily continuous in physical structure , When a linear table is physically stored , It is usually stored in the form of array and chain structure .

2. The order sheet

2.1 Concept and structure

A sequence table is a linear structure in which data elements are sequentially stored in a section of storage cells with continuous physical addresses , Generally, array storage is used
Store . Add, delete, check and modify the data on the array

2.2 Realization

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;


typedef struct SeqList
{
	SLDataType* a;// Pointer to dynamic array 
	int size;// The number of data 
	int capacity;// Capacity 
}SL;



// initialization 
void SLInit(SL* ps);

void SLCheckCapacity(SL* ps);

void SLPrint(SL* ps);

// Tail insertion / Deletion at the end 
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);

// Head insertion / Head deletion 
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);


// Insert delete anywhere 
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

// Find and modify 
int SLFind(SL* ps, SLDataType x);
void SLModify(SL* ps, int pos, SLDataType x);

SeqList.c

#include "SeqList.h"


void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}


void SLCheckCapacity(SL* ps)
{
	assert(ps);

	// Check capacity space , Full capacity expansion 
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : (ps->capacity * 2);
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("SLCheckCapacity::SL* tmp:");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newCapacity;
		}
	}
	return;
}

void SLPrint(SL* ps)
{
	assert(ps);
	for (int i = 0;i < ps->size;i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SLPushBack(SL* ps, SLDataType x)
{
	//assert(ps);
	//SLCheckCapacity(ps);
	//ps->a[ps->size] = x;
	//ps->size++;

	SLInsert(ps, ps->size,x);
}

void SLPopBack(SL* ps)
{
	//assert(ps);
	//assert(ps->size > 0);
	//ps->size--;

	SLErase(ps, ps->size -1);
}

void SLPushFront(SL* ps, SLDataType x)
{
	//assert(ps);
	//SLCheckCapacity(ps);
	//for (int end = ps->size;end > 0;end--)
	//{
	//	ps->a[end] = ps->a[end - 1];
	//}
	//ps->a[0] = x;
	//ps->size++;

	SLInsert(ps, 0, x);
}


void SLPopFront(SL* ps)
{
	//assert(ps->size > 0);
	//assert(ps);
	//for (int start = 0;start < ps->size - 1;start++)
	//{
	//	ps->a[start] = ps->a[start + 1];
	//}
	//ps->size--;

	SLErase(ps, 0);
}

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int end = ps->size;end > pos;end--)
	{
		ps->a[end] = ps->a[end - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int start = pos;start < ps->size-1;start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;
}


int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0;i < ps->size;ps++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

3. Linked list

3.1 The concept and structure of linked list

Concept ： A linked list is a physical storage structure that is not continuous 、 Nonsequential storage structure , The logical order of data elements is through the linked list
Pointer link order in .

 

3.2 The classification of the list

In practice, the structure of linked list is very diverse , The combination of the following is 8 A linked list structure ：

1. One way or two way

2. Take the lead or not

3. Cyclic or acyclic

In practice, we usually use two kinds of structures ：

 3.3 The realization of linked list

3.3.1  Headless + A one-way + Implementation of addition, deletion, query and modification of acyclic linked list

Slist.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;


typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


SLTNode* BuySListNode(SLTNode x);
// Printing of single linked list 
void SListPrint(SLTNode* plist);

// Tail insertion of single linked list 
void SListPushBack(SLTNode** plist, SLTDataType x);
// Single chain head plug in 
void SListPushFront(SLTNode** plist, SLTDataType x);
// Delete the end of the single list 
void SListPopBack(SLTNode** plist);
// Delete the single chain header 
void SListPopFront(SLTNode** plist);
// Single linked list lookup 
SLTNode* SListFind(SLTNode* phead, SLTDataType x);

void SListInsertAfter(SLTNode* pos, SLTDataType x);

void SListEraseAfter(SLTNode* pos);

SList.c
#include"SList.h"


SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SListPrint(SLTNode* plist)
{
	while (plist != NULL)
	{
		printf("%d->", plist->data);
		plist = plist->next;
	}
	printf("NULL\n");
}


void SListPushBack(SLTNode ** plist, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	SLTNode* ptail = *plist;
	if (*plist == NULL)
	{
		*plist = newnode;
	}
	else
	{
		while ((ptail)->next)
		{
			(ptail) = (ptail)->next;
		}
		(ptail)->next = newnode;
	}
}

void SListPushFront(SLTNode** plist, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *plist;
	*plist = newnode;
}

void SListPopBack(SLTNode** plist)
{
	assert(*plist);
	SLTNode* ptail = *plist;
	// There is only one node 
	if ((*plist)->next == NULL)
	{
		free(*plist);
		*plist = NULL;
		return;
	}
	// Multiple nodes 
	while (ptail->next->next)
	{		
		ptail = ptail->next;
	}
	free(ptail->next);
	ptail->next = NULL;
}


void SListPopFront(SLTNode** plist)
{
	assert(*plist);
	SLTNode* phead = *plist;
	*plist = (phead)->next;
	free(phead);
	phead = NULL;
}

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}

	return NULL;
}

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
		return;
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

3.3.2  Take the lead + two-way + The implementation of adding, deleting, checking and modifying the circular linked list

List.h
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>



typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;


LTNode* BuyListNode(LTDataType x);
LTNode* ListInit();
void ListPrint(LTNode* phead);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
//  stay pos Insert before position x
void ListInsert(LTNode* pos, LTDataType x);
//   Delete pos The nodes of the location 
void ListErase(LTNode* pos);

List.c
#include"List.h"



LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

LTNode* ListInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void ListPrint(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	//LTNode* newnode = BuyListNode(x);
	//LTNode* tail = phead->prev;
	//tail->next = newnode;
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;

	ListInsert(phead, x);
}

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	//LTNode* newnode = BuyListNode(x);
	//LTNode* next = phead->next;
	//next->prev = newnode;
	//newnode->next = next;
	//phead->next = newnode;
	//newnode->prev = phead;

	ListInit(phead->next, x);
}

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	//LTNode* del = phead->prev;
	//LTNode* pre = del->prev;
	//pre->next = phead;
	//phead->prev = pre;
	//free(del);

	ListErase(phead->prev);
}

void ListPopFront(LTNode* phead)
{
	//assert(phead);
	//assert(phead->next != phead);
	//LTNode* del = phead->next;
	//LTNode* next = del->next;
	//free(del);
	//phead->next = next;
	//next->prev = phead;

	ListErase(phead->next);
}

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* pre = pos->prev;
	pre->next = newnode;
	newnode->prev = pre;
	newnode->next = pos;
	pos->prev = newnode;
}

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* pre = pos->prev;
	LTNode* next = pos->next;
	pre->next = next;
	next->prev = pre;
	free(pos);
}

4. Advantages and disadvantages of sequence list and chain list

	advantage	shortcoming
The order sheet	1. Support random access 2.cpu High cache hit rate	Low efficiency of head or middle insertion , Capacity expansion ( A certain degree of performance consumption , There may be some waste of space )
Linked list ( Take the lead + two-way + Circular linked list )	1. Insert delete anywhere O(1) 2. Apply for release on demand	Subscript random access is not supported