Rambling data Structures (II) — Linear Table 2

The author’s personal blog www.you3xuan.top/ view the original article. This is the second linear table, if you want to read the first, please click here. Source code address: github.com/ThinkingXua… If it is helpful to you, please use a Star.

1, linear list chain storage

In chained storage, the addresses of memory cells between nodes are discontinuous. Each node contains the data field and the address of the next node. The header data field only stores the length of the node and points to the first element. The tail points to NULL. As shown in the figure:

2, the implementation of chain storage

2.1 Creating singly linked lists

There are three parts: creating a header node, creating a common node, and creating a single linked list.

1. Create a header

// create a header. Length stores the length of the list. Next points to the next node
typedef struct Header{
	int length;
	struct Header * next;
}Head;
Copy the code

2. Create a normal node

// Create a node, data stores the data, next points to the next node
typedef struct Node{
	int data;
	struct Node *next; 
}ListNode;
Copy the code

3. Create a list

// Create a linked list and return the header
Head * createList(a){
	Head *phead = (Head*)malloc(sizeof(Head));
	phead->length = 0;
	phead->next = NULL;
	return phead;
}

Copy the code

2.2 Obtaining the Length of the Linked List

Int getLength(Head * phead){if(phead==NULL){
		printf("not init headnode! \n");
		return- 1; }return phead->length;
} 
Copy the code

2.3 Adding a Node

// Add data, which is added at the end by default
int addData(Head * phead, int data){
	if(phead==NULL) {printf("not init head node! \n");
		return - 1;
	}	
	
	// Create the current node and point to the last node in the list
	ListNode * curNode = phead;
	while(curNode->next! =NULL){
		curNode = curNode->next;
	}
	
	// Create new node
	ListNode * newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->data = data;
	newNode->next = NULL;
	
	// Join the node
	curNode->next = newNode;
	phead->length++;
	return 1;		
} 

Copy the code

As shown in the figure, adding a node requires two nodes, one is the current node, pointing to the tail node, and the other is the new node to be added, pointing to NULL. Using the next of the current node to point to the new node, the operation of adding a node is complete. Because the current node points to the tail node, the next of the current node is equivalent to the next of the tail node, so the next of the tail node points to the new node. Finally, don’t forget to increase the length of the head node by 1.

2.4 Inserting nodes

// Insert data
int insertData(Head * pHead, int data, int pos){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	if(pos < 0||pos > pHead->length){
		printf("insert postion error! \n");
		return 2 -;
	}
	
	// Create new node
	ListNode * newNode = (ListNode *)malloc(sizeof(ListNode));
	newNode->data = data;
	
	// Create the current node
	ListNode * curNode = pHead;
	int i;
	for(i=0; i<pos; i++){ curNode = curNode->next; } newNode->next = curNode->next; curNode->next = newNode; pHead->length++;return 1; 
}
Copy the code

Similarly, insertion requires two nodes, one of which points to the node before the insertion, called the current node. The other node is the new node. Basically two lines of code:

newNode->next = curNode->next;
curNode->next = newNode;
Copy the code

The current node points to the previous node to be inserted and is named lastNode. The above code is equivalent to:

newNode->next = lastNode->next;
lastNode->next = newNode;
Copy the code

Because lastNode->next points to the next node. Now use newNode->next to point to the next node. Then use lastNode-> Next to point to newNode. You’re done inserting. Two lines of code cannot be reversed, because executing the second line first will cause all subsequent nodes to be lost.

2.5 Deleting a Node

// Delete data
int deleteData(Head * pHead,int pos){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	if(pos < 0||pos >= pHead->length){
		printf("delete postion error! \n");
		return 2 -;
	}
	
	// Create the current node
	ListNode * curNode = pHead;
	
	int i;
	for(i=0; i<pos; i++){ curNode = curNode->next; } curNode->next = curNode->next->next; pHead->length--;return 1;
} 
Copy the code

next
curNode->next = curNode->next->next

2.6 Obtaining the node at the specified position

// Get data
int getData(Head * pHead,int pos){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	if(pos < 0||pos >= pHead->length){
		printf("postion error! \n");
		return 2 -;
	}
	
	// Create the current node
	ListNode * curNode = pHead;
	int i;
	for(i=0; i<=pos; i++){ curNode = curNode->next; }return curNode->data;
} 

Copy the code

2.7 Printing all nodes

/ / print
void print(Head * phead){
	if(phead==NULL) {printf("not init headnode! \n");
		return 0;
	}

	ListNode * node = phead->next;
	while(node->next! =NULL) {printf("%d->",node->data);
		node = node->next;
	}
	printf("%d length=%d\n",node->data,phead->length);
}
Copy the code

For better printing, the idea is to remove the last -> and print the length of the list.

2.8 test

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

int main(a){
	int i;
	printf("create ListNode:\n");
	Head* pHead = createList();
	printf("length=%d\n\n",pHead->length);
	
	printf("add data:\n");
	for(i=0; i<10; i++){ addData(pHead,i); } print(pHead) ;printf("\n");
	
	printf("insert data:\n");
	insertData(pHead,100.3);
	print(pHead);
	printf("\n");
	
	printf("delete data:\n");
	deleteData(pHead,3);
	print(pHead);
	printf("\n");
	
	printf("get data:\n");
	printf("%d\n",getData(pHead,5));
	printf("\n");
	
	return 0;
}
Copy the code

Output result:

3, double linked list to achieve chain storage

define

The previous use of a single linked list to achieve linear list chain storage. But single-linked lists have the disadvantage of not being able to access the precursor nodes. When you find an element node, if you want to find the previous element node, you have to start from the beginning, which is very troublesome. All doubly linked lists create a space that stores the addresses of their predecessors. As shown in the figure:

The implementation of a double linked list is similar to a single linked list. When we insert a new node, if the node has a back driver, if the back driver’s Pre points to the new node, the new node’s Pre also points to its front driver. The other operations are similar, but the code is posted here and not explained in detail.

3.1 Creating double-linked lists

typedef struct Header{
	int length;
	struct Header * pre;  // Add a pre to the Head Node for convenience, otherwise you can't point to Node.
	struct Header * next;
}Head;

typedef struct Node{
	int data;
	struct Node * pre;          
	struct Node * next;
}NodeList;

/ / create
Head * createDouNodeList(a){
	Head * pHead = (Head*)malloc(sizeof(Head));
	if(pHead == NULL) {printf("create failure! \n"); 
	} 
	pHead->length = 0;
	pHead->next = NULL;
	return pHead;
}

Copy the code

3.2 Obtaining the length of the list

// Get the list length
int getLength(Head * pHead){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	return pHead->length;
}
Copy the code

3.3 Checking whether the disk is empty

// Check whether it is null
int isEmpty(Head *pHead){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	if(pHead->length==0) {return 1;
	}else{
		return 0; }}Copy the code

3.4 Adding a Node

// Add node,, default added at the end
int addDataDou(Head * pHead, int data){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}	
	// Create the current node and point to the last node in the list
	NodeList * curNode = pHead; 

	while(curNode->next ! =NULL){
		curNode = curNode->next;
	}

	// Create new node
	NodeList * newNode = (NodeList*)malloc(sizeof(NodeList));
	newNode->data = data; 
	newNode->next = NULL;
	
	curNode->next = newNode;
	newNode->pre = curNode;
	pHead->length++;
	return 1;
} 

Copy the code

3.5 Inserting nodes

/ / insert
int insertDou(Head *pHead,int data,int pos){
	
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	} 
	if(pos<=0||pos>=pHead->length){
		printf("insert positon error! \n");
		return 2 -;		
	}
	// Create new node
	NodeList * newNode = (NodeList*)malloc(sizeof(NodeList));
	newNode->data = data;
	 
	// Create the current node and point to the node before the specified location
	NodeList * curNode = pHead;
	int i;
	for(i=0; i<pos; i++){ curNode = curNode->next; }/ / the connection
	newNode->next = curNode->next;
	curNode->next->pre = newNode;
	newNode->pre = curNode;
	curNode->next = newNode;
	
	pHead->length++;
	
	return 1;
} 

Copy the code

3.6 Deleting a Node

/ / delete
int deleteDataDou(Head * pHead,int pos){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	if(pos < 0||pos >= pHead->length){
		printf("delete postion error! \n");
		return 2 -;
	}
	
	// Create the current node
	NodeList * curNode = pHead;
	
	int i;
	for(i=0; i<pos; i++){ curNode = curNode->next; } curNode->next = curNode->next->next;// Delete the last node
	if(curNode->next! =NULL){
		curNode->next->pre = curNode; 
	}
	
	pHead->length--;
	return 1;
} 
Copy the code

3.7 Getting the node of the specified element

// Find an element and return its node
NodeList * findNodeDou(Head *pHead,int val){
	if(pHead==NULL) {printf("not init head node! \n");
		return 0;
	}
	NodeList *curNode = pHead->next;
	do{
		if(curNode->data == val){
			return curNode;
		}
		curNode = curNode->next;
		
	}while(curNode->next! =NULL);
	return NULL;
} 
Copy the code

3.8 Printing all nodes

/ / print
void print(Head * pHead){
	if(pHead==NULL) {printf("not init head node! \n");
		return 0;
	}
	NodeList * node = pHead->next;
	while(node->next! =NULL) {printf("%d<->",node->data);
		node = node->next;
	}
	printf("%d length=%d\n",node->data,pHead->length);
}
Copy the code

3.9 test

// Double linked lists implement chained storage
 #include <stdio.h>
 #include <stdlib.h>
 
int main(a){
	int i;
	
	printf("Create Double Node List: \n"); 
	Head  *pHead =  createDouNodeList();
	printf("length = %d\n",pHead->length);
	printf("\n");
	
	printf("Add Data: \n");
	for(i=0; i<10; i++){ addDataDou(pHead,i); } print(pHead);printf("\n");	
	
	printf("Insert Data: \n");
	insertDou(pHead,100.3);
	print(pHead);
	printf("\n");	
	
	printf("delete Data: \n");
	deleteDataDou(pHead,3);
	print(pHead);
	printf("\n");
	
	printf("find Node: \n");
	NodeList * node = findNodeDou(pHead,3);
	printf("node is %d\n",node);
	printf("\n");
	
	return 0;
} 

Copy the code

Output result:

Circular linked lists

Another common form of a linked list is a circular list. Starting from any node in the list, you can find all the other nodes.

Cyclic lists are divided into unidirectional cyclic lists, double cyclic lists and multiple cyclic lists. As shown in the figure:

This tutorial only covers one-way circular lists. The other two are more complex, so search for them yourself if you need to. The creation and lookup of a circular list is basically the same as a single list, so I’m not going to talk more about it here, just insert and delete. If you are not sure, please read the previous knowledge carefully.

4.1 Inserting nodes

int insertCircleList(Head * pHead,int data,int pos){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	if(pos < 0||pos > pHead->length){
		printf("insert postion error! \n");
		return 2 -;
	}
	
	// Create new node
	NodeList * newNode = (NodeList*)malloc(sizeof(NodeList));
	newNode->data = data;
	
	// If it is empty
	if(isEmpty(pHead)){
		pHead->next = newNode;   // Insert directly after the header
		newNode->next = newNode; // Point yourself to yourself
	}else{
		
		NodeList *curNode = pHead->next;
		
		// Because pos ==0 is involved in the end node, it is handled separately
		if(pos==0) {//curNode points to the end node
			while(curNode->next! =pHead->next){ curNode = curNode->next; } newNode->next =pHead->next; pHead->next = newNode; curNode->next = newNode; }else{
			// Make curNode point to the node before the insertion position
			int i;
			for(i=1; i<pos; i++){ curNode = curNode->next; } newNode->next = curNode->next; curNode->next = newNode; } } pHead->length++;return 1;
}
Copy the code

4.2 Deleting a Node

int deleteCircleNode(Head *pHead,int pos){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	if(pos < 0||pos > pHead->length){
		printf("insert postion error! \n");
		return 2 -;
	}
	
	NodeList *curNode = pHead->next;
	
	if(isEmpty(pHead)){
		return - 3;
	}else{
		if(pos==0) {while(curNode->next! =pHead->next){ curNode = curNode->next; } curNode->next = curNode ->next->next; pHead->next = curNode ->next; }else{
			int i;
			for(i=1; i<pos; i++){ curNode = curNode->next; } curNode ->next = curNode->next->next; } } pHead->length--;return 1; 
} 
Copy the code

4.3 Other Codes

// create a header. Length stores the length of the list. Next points to the next node
typedef struct Header{
	int length;
	struct Header * next;
}Head;

// Create a node, data stores the data, next points to the next node
typedef struct Node{
	int data;
	struct Node *next; 
}NodeList;

// Create a linked list and return the header
Head * createList(a){
	Head *phead = (Head*)malloc(sizeof(Head));
	phead->length = 0;
	phead->next = NULL;
	return phead;
}

// Check whether it is null
int isEmpty(Head *pHead){
	if(pHead==NULL) {printf("not init head node! \n");
		return - 1;
	}
	if(pHead->length==0) {return 1;
	}else{
		return 0; }}/ / print
void print(Head *pHead){
	if(pHead==NULL) {printf("not init headnode! \n");
		return 0;
	}

	NodeList * node = pHead->next;
	do{
		printf("%d->",node->data);
		node = node->next;
	}while(node! =pHead->next);printf(" length=%d\n",pHead->length);
}
Copy the code

4.4 test

// loop linked lists
#include<stdio.h>
#include<stdlib.h>
int main(a){
	int i;
	printf("Create Circle Node List: \n");
	Head * pHead = createList();
	printf("length = %d\n",pHead->length);
	printf("\n");
	
	printf("Insert Node: \n");
	for(i=0; i<11; i++){ insertCircleList(pHead,i,i); } print(pHead);printf("\n");
	
	printf("Delete Node: \n");
	deleteCircleNode(pHead,0);
	print(pHead);
	return 0;
}
Copy the code

Output result: