Concept and structure of linked list

Concept: linked list is a non continuous and non sequential storage structure in physical storage structure. The logical order of data elements is realized through the pointer link order in the linked list.

• Chain structure is logically continuous, but not necessarily continuous physically
• In reality, nodes are generally applied from the heap
• The space applied from the heap is allocated according to certain strategies. The space applied for two times may or may not be continuous

In fact, the structure of the linked list is very diverse. There are eight linked list structures combined.

1. One way or two-way

2. Take the lead or not

3. Cycle and non cycle

This paper introduces a headless one-way acyclic linked list.

Headless one-way acyclic linked list: it has a simple structure and is generally not used to store data alone. In fact, it is more used as a substructure of other data structures, such as hash bucket, adjacency table of graph and so on. In addition, this structure appears a lot in the written interview.

SListNode node structure

A linked list is linked by a node, so before creating a linked list, you must first create a node. The node consists of two parts: data field and pointer field.

typedef int SLTDataType;

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

Function interface

// Dynamically apply for a node
SLTNode* BuySListNode(SLTDataType x);
// Single linked list printing
void SListPrint(SLTNode* phead);
// Single chain table tail insertion
void SListPushBack(SLTNode** pphead, SLTDataType x);
// Single chain meter insertion
void SListPushFront(SLTNode** pphead, SLTDataType x);
// Single chain tail deletion
void SListPopBack(SLTNode** pphead);
// Single chain header deletion
void SListPopFront(SLTNode** pphead);
// Single linked list lookup
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// The single linked list inserts an x after the pos position
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// Value after deleting pos position in single linked list
void SListEraseAfter(SLTNode* pos);
// Destruction of single linked list
void SListDestroy(SLTNode** pphead);

The above functions are realized below.

Print single linked list

To print a single linked list, you need to start from the position pointed by the pointer and print back in turn until the pointer points to NULL.

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

Single chain table tail insertion

void SListPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		SLTNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newnode;
	}

}

be careful:

1. assert(pphead) here; This is to prevent passing in a pointer that is not a second level pointer.
2. When adding a node to a single linked list, we need to apply for a new node, so we might as well encapsulate this function into a function.

SLTNode* BuySListNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

Single chain meter insertion

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

Single chain tail deletion

Note:

1. Secondary pointer required
2. For empty linked list, one node, two or more nodes are discussed

void SListPopBack(SLTNode** pphead) {
	assert(*pphead != NULL);

	// A node
	if ((*pphead)->next == NULL) {
		free (*pphead);
		*pphead = NULL;
	}
	else {
		// Two or more nodes
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL) {
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

Single chain header deletion

be careful:

1. You need to determine whether it is an empty linked list.
2. Update header pointer

void SListPopFront(SLTNode** pphead) {
	assert(*pphead != NULL);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

Find node

Traverse the linked list. If it is found, it returns the current node. Otherwise, it returns NULL.

SLTNode* SListFind(SLTNode* phead, SLTDataType x) {
	for (SLTNode* cur = phead; cur != NULL; cur = cur->next) {
		if (cur->data == x) {
			return cur;
		}
	}
	return NULL;
}

The single linked list inserts an x after the pos position

First of all, this leads to a question: why should I choose to insert after pos instead of before pos?
In fact, there is a reason. If you just insert after pos, you can operate without traversing the linked list; If you want to insert before pos, you need to traverse the linked list. However, the time overhead is large (compared with O(N)).

Attention

1. Judge whether it belongs to tail insertion
2. Order of inserting nodes!!! Cannot be reversed
   newnode->next = pos->next;
   pos->next = newnode;

void SListInsertAfter(SLTNode* pos, SLTDataType x) {
	SLTNode* newnode = BuySListNode(x);
	if (pos->next == NULL) {
		// Tail insertion
		pos->next = newnode;
	}
	else {
		newnode->next = pos->next;
		pos->next = newnode;
	}
}

Value after deleting pos position in single linked list

void SListEraseAfter(SLTNode* pos) {
	assert(pos && pos->next);

	SLTNode* next = pos->next->next;
	free(pos->next);
	pos->next = NULL;
	pos->next = next;
}

Single linked list destruction

be careful
To destroy a single linked list, you need to destroy the nodes one by one.
Why?
Just because it is developed on the heap one by one, unlike the dynamic development of the sequence table, it is a continuous memory space in the memory. If you only perform free(*pphead) operation on the linked list, it will cause memory leakage!!!

void SListDestroy(SLTNode** pphead) {
	SLTNode* cur = *pphead;
	while (cur) {
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

Finally

In fact, the single chain watch is not so terrible. The terrible thing is that the teacher is confused in class (dog head saves life hhh). We just need to imagine it as one carriage of the train~~~

Car, doodle doodle!!!

Finally, if you like bloggers, you might as well pay attention! It's not easy to write code. Be grateful (´ ᴗᴗ`) than heart