REN

Linked Lists are pointer based data structure. Compared with Arrays, Linked Lists have several advantages such as dynamic length, no need to be physical consecutive. This article made a very detailed description on LinkedList operations in C Language. Linked Lists are quite easy and 'original' when being implemented by C language because they're based on pointers.

Single Linked Lists

Single linked list means the node of a single linked list could only point to the next node instead of the prior node. Here's the general definition for a node of Single Linked List:

typedef struct SNode {
	elementType value;
	struct SNode *next;
} SNode;

Note that the value field could be any other types. And the pointer of SNode points to the next node of the Linked List. Thus the SNode structure is a recursive structure. An node that lays in heap, typically gets the dynamic memory by malloc/calloc. In this article, I'm gonna make the linked lists with dummy head node because without dummy head node, some operations such as insertion and delete need to seperate the condition of first node and non-first node. Now let's take a look at basic methods and operations of a single linked list.

Create

To reate a single Linked List, an dummy node need to be allocated.

void CreateList(){
	SNode *list = (SNode*)malloc(sizeof(SNode));
	if (NULL != list) {
		list->value = -1;
		list->next = NULL;
	}
	return list;
}

Insert From Head

Insert an node from the head of a linked list. Be aware of that make the newly inserted node pointing to the next node before making the dummy node pointing to the newly inserted node; Otherwise the list is gonna be unlinked.

int InsertFromHead(SNode* list, elementType value){
	if (NULL == list)
		return -1;
	SNode *node = (SNode*)malloc(sizeof(SNode));
	if (NULL == node)
		return -1;
	node->value = value;
	node->next = list->next;	// (1)
	list->next = node;		// (2)
	return 0;
}

Insert To Tail

Insert an node to the tail of a linked list. Set an pointer of SNode p firstly pointing to the dummy node of the linked list; Then moving it forward until the next of p is not NULL.

int InsertToTail(SNode* list, elementType value){
	if (NULL == list)
		return -1;
	SNode *p = list;
	while (NULL != p->next)
		p = p->next;
	SNode *node = (SNode*)malloc(sizeof(SNode));
	if (NULL == node)
		return -1;
	node->value = value;
	node->next = p->next;	// (1)
	p->next = node;		// (2)
	return 0;
}

Find By Value

Walk through the linked list, and find the node whose value equals to the value you need to find; Return the pointer of SNode you need to find. This operation is quite simple, and time complexity is O(n).

SNode* FindByValue(SNode* list, elementType value){
	if (NULL == list)
		return list;
	SNode *p = list->next;
	while (NULL != p) {
		if (value = p->value)
			return p;
		p = p->next;
	}
	return NULL;
}

Delete By Value

Delete the node in a linked list if value of this node equals to the value you want. In this operation, we need to pointers q pointing to the node you need to delete and p pointing the node prior to that respectively; Otherwise after deleting, the linked list is no longer be linked. Last but not least, don't forget to free the memory of the node just being deleted.

int DeleteByValue(SNode* list, elementType value){
	if (NULL == list)
		return -1;
	SNode *p = list;
	SNode *q = p->next;
	while (NULL != q) {
		if (value == q->value) {
			p->next = q->next;	// (1)
			free(q);		// (2)
			return 0;
		}
		p = q;
		q = q->next;
	}
	return -1;
}

Reverse List

Reverse a single linked list is quite tricky, the head is gonna pointing to the last node while the first node will become the last node. To reverse it, we need to set a constant pointer b pointing to the orignal head node and then set a moving-forward pointer q, each iteration q begins to point to the current head; Finally, move head forward.

int ReverseList(SNode* list){
	if (NULL == list && NULL == list->next)
		return -1;
	SNode *p = list->next;
	SNode *q;
	while (NULL != p->next) {
		q = p->next;		// (1)
		p->next = q->next;	// (2)
		q->next = list->next;	// (3)
		list->next = q;		// (4)
	}
	return 0;
}

Print List Reversely

To print a single list reversely, there're several methods. One is that using the ReverseList() I illustrated just now, and then print the reversed one by sequence. The easiest way to do so is to use the key point of stack and recursive function call.

void PrintListReversely(SNode* list){
	if (NULL == list && NULL == list->next)
		return;
	PrintListReversely(list->next);
	printf("%d ", list->next->data);
}

Double Linked Lists

Double linked list means the node of a double linked list could not only point to the next node but also point the prior node. Here's the general definition for a node of Double Linked List:

typedef struct DNode {
	elementType value;
	struct DNode *next;
	struct DNode *prev;
} SNode;

In the following discussion, I'll make the double list circular, which means the last node pointing to the first node and the first node also pointing to the last node.

Create

To reate a double Linked List, an dummy node need to be allocated. Note that at the beginning of creating the dummy node, both its next and prev pointing to itself.

DNode* createList() {
	// Create a dummy node for a sinle linked list
	DNode* list = (DNode*)malloc(sizeof(DNode));
	if (NULL != list) {
		list->value = -1;
		list->prev = list;
		list->next = list;
	}
	return list;
}

Insert From Head

Insert from head in a double linked list is no more difficult than that in a single linked list.

int insertFromHead(DNode* list, type value) {
	if (NULL == list)
		return -1;
	DNode* node = (DNode*)malloc(sizeof(DNode));
	if (NULL == node)
		return -1;
	node->value = value;
	node->next = list->next;	// (1)
	node->prev = list;		// (2)
	list->next->prev = node;	// (3)
	list->next = node;		// (4)
	return 0;
}

Insert To Tail

Insert to tail is just the same logic as insert from head, just need to move the pointer to the last node.

int insertToTail(DNode* list, type value) {
	if (NULL == list)
		return -1;
	DNode* node = (DNode*)malloc(sizeof(DNode));
	DNode* p = list;
	if (NULL == node)
		return -1;
	while (list != p->next)
		p = p->next;
	node->value = value;
	node->next = p->next;	// (1)
	node->prev = p;		// (2)
	p->next->prev = node;	// (3)
	p->next = node;		// (4)
	return 0;
}

Delete By Value

Delete node by value in a double linked list is no more difficult than that in a single linked list.

int deleteByValue(DNode* list, type value) {
	if (NULL == list)
		return -1;
	DNode* p = list;
	DNode* q = list->next;
	while (list != q) {
		if (q->value == value) {
			p->next = q->next;	// (1)
			q->next->prev = p;	// (2)
			free(q);		// (3)
			return 0;
		}
		p = q;
		q = q->next;
	}
	// not found
	return -1;
}