C/C + + learning notes -- C improvement: linked list

Basic concepts of linked list

What is a linked list

  • Linked list is a kind of common data structure. It connects some column data nodes into a data chain by pointer. Compared with array, linked list has better dynamic (non sequential storage).
  • The data domain is used to store data, and the pointer domain is used to establish a connection with the next node.
  • When building a linked list, you can allocate space randomly without knowing the total amount of data in advance, and you can insert or delete data at any position in the linked list in real time.
  • The cost of linked list is mainly the access sequence and the space loss of organization chain.

Differences between arrays and linked lists:
Array: allocate a contiguous storage area at a time.
Advantages: high efficiency of random access to elements
Disadvantages: 1) a continuous storage area needs to be allocated (large area may fail to allocate)
2) Deleting and inserting an element is inefficient
Linked list: there is no need to allocate a continuous storage area at one time, only n storage areas of nodes need to be allocated, and the relationship is established through pointers.
Advantages: 1) no need for a continuous storage area
2) Deleting and inserting an element is efficient
Disadvantage: random access to elements is inefficient

Reference to structure itself

Question 1: can a struct be nested with this type of struct variable?
Question 2: can structs nest pointer variables of this type?

typedef struct _STUDENT{
	char name[64];
	int age;
}Student;

typedef struct _TEACHER{
	char name[64];
	Student stu; //Structs can nest other types of structs
	//Teacher stu;
	//Struct · Teacher teacher; / / at this time, the member of the Teacher type has not been determined. The compiler cannot allocate memory
	struct _TEACHER* teacher; //No matter what type of pointer, it only takes 4 bytes, and the compiler can determine the memory allocation
}Teacher;
  • A structure can nest any type of variable of another structure;
  • Structure nested common variables of this structure (not allowed). The type size of this structure cannot be determined. Type nature: fixed size memory block alias;
  • The structure is nested with pointer variables (OK) of the structure. The space of pointer variables can be determined, 32-bit, 4-byte, 64 bit, 8-byte;

struct Node

Let's think about it. We say that the linked list is composed of a series of nodes. So how to represent a node that contains a data field and a pointer field?
The node type of the linked list is actually a structure variable, which contains data field and pointer field:

  • Data domain is used to store data;
  • The pointer field is used to establish a connection with the next node. When this node is a tail node, the value of the pointer field is NULL;
typedef struct Node 
{
	//Data domain
	int id;
	char name[50];

	//Pointer domain
	struct Node *next;       
}Node;

Classification of linked list

The list is divided into static list and dynamic list
Static list and dynamic list are two different representations of linear list chain storage structure

  • All nodes are defined in the program, not opened temporarily, and cannot be released after use. This kind of list is called "static list".
  • The so-called dynamic linked list refers to the establishment of a linked list from scratch in the process of program execution, that is, to open up nodes and input data of each node one by one, and establish the relationship between the front and back links.

Static linked list

typedef struct Stu
{
	int id;	//Data domain
	char name[100];

	struct Stu *next; //Pointer domain
}Stu;

void test()
{
	//Initialize three struct variables
	Stu s1 = { 1, "yuri", NULL };
	Stu s2 = { 2, "lily", NULL };
	Stu s3 = { 3, "lilei", NULL };

	s1.next = &s2; //The next pointer of s1 points to s2
	s2.next = &s3;
	s3.next = NULL; //Tail node

	Stu *p = &s1;
	while (p != NULL)
	{
		printf("id = %d, name = %s\n", p->id, p->name);

		//Node moves one bit backward
		p = p->next; 
	}
}

dynamic chain

typedef struct Stu{
	int id;	//Data domain
	char name[100];

	struct Stu *next; //Pointer domain
}Stu;

void test(){
	//Dynamic allocation of 3 nodes
	Stu *s1 = (Stu *)malloc(sizeof(Stu));
	s1->id = 1;
	strcpy(s1->name, "yuri");

	Stu *s2 = (Stu *)malloc(sizeof(Stu));
	s2->id = 2;
	strcpy(s2->name, "lily");

	Stu *s3 = (Stu *)malloc(sizeof(Stu));
	s3->id = 3;
	strcpy(s3->name, "lilei");

	//Establish the relationship between nodes
	s1->next = s2; //The next pointer of s1 points to s2
	s2->next = s3;
	s3->next = NULL; //Tail node

	//Traversing node
	Stu *p = s1;
	while (p != NULL)
	{
		printf("id = %d, name = %s\n", p->id, p->name);

		//Node moves one bit backward
		p = p->next; 
	}

	//Free node space
	p = s1;
	Stu *tmp = NULL;
	while (p != NULL)
	{
		tmp = p;
		p = p->next;

		free(tmp);
		tmp = NULL;
	}
}

Lead and no lead lists

  • Lead linked list: a node is fixed as the head node (the data field does not save valid data), which acts as a flag bit. In the future, the head node is fixed regardless of the change of the linked list node.

  • No head linked list: the head node is not fixed. Change the head node according to the actual needs (for example, insert a new node before the original head node, and then the new node will be the head node of the linked list again).

One way list, two-way list, circular list

One way list:

Double linked list:

Circular list:

Basic operation of linked list

Create linked list

Use the structure to define the node type:

typedef struct _LINKNODE
{
	int id; //Data domain
	struct _LINKNODE* next; //Pointer domain
}link_node;

Write a function: link? Node * init? Linklist()
A one-way linked list with head nodes is established, and nodes are created in cycles. The values in the node data field are input from the keyboard, with - 1 as the input end flag, and the head node address of the linked list is returned by the function value

typedef struct _LINKNODE{
	int data;
	struct _LINKNODE* next;
}link_node;

link_node* init_linklist(){
	
	//Create head node pointer
	link_node* head = NULL;
	//Allocate memory to the head node
	head = (link_node*)malloc(sizeof(link_node));
	if (head == NULL){
		return NULL;
	}
	head->data = -1;
	head->next = NULL;

	//Save current node
	link_node* p_current = head;
	int data = -1;
	//Loop to insert a node into a linked list
	while (1){
	
		printf("please input data:\n");
		scanf("%d",&data);

		//Exit loop if - 1 is entered
		if (data == -1){
			break;
		}

		//Allocate memory to new nodes
		link_node* newnode = (link_node*)malloc(sizeof(link_node));
		if (newnode == NULL){
			break;
		}

		//Assign a value to a node
		newnode->data = data;
		newnode->next = NULL;

		//The new node is put into the linked list, that is, the node is inserted into the next position of the last node
		p_current->next = newnode;
		//Update auxiliary pointer P "current
		p_current = newnode;
	}

	return head;
}

Traversing linked list

Write a function: void foreach ﹣ linklist (link ﹣ node * head)
Output the contents of each node data field of unidirectional linked list in sequence:

//Traversing linked list
void foreach_linklist(link_node* head){
	if (head == NULL){
		return;
	}

	//Assignment pointer variable
	link_node* p_current = head->next;
	while (p_current != NULL){
		printf("%d ",p_current->data);
		p_current = p_current->next;
	}
	printf("\n");
}

Insertion node

Write function: void insert klist (link_node * head, int Val, int data)
Insert data after the specified value, or at the end if val does not exist.

//Insert node before value val
void insert_linklist(link_node* head, int val, int data){
	
	if (head == NULL){
		return;
	}

	//Two auxiliary pointers
	link_node* p_prev = head;
	link_node* p_current = p_prev->next;
	while (p_current != NULL){
		if (p_current->data == val){
			break;
		}
		p_prev = p_current;
		p_current = p_prev->next;
	}

	//If p'current is NULL, there is no node with value val
	if (p_current == NULL){
		printf("No value exists%d Node!\n",val);
		return;
	}

	//Create a new node
	link_node* newnode = (link_node*)malloc(sizeof(link_node));
	newnode->data = data;
	newnode->next = NULL;

	//New node into linked list
	newnode->next = p_current;
	p_prev->next = newnode;
}

Delete node

Write function: void remove klist (link_node * head, int VAL)
Delete the first node with val value

//Delete node with val value
void remove_linklist(link_node* head,int val){
	if (head == NULL){
		return;
	}

	//Auxiliary pointer
	link_node* p_prev = head;
	link_node* p_current = p_prev->next;

	//Find node with val value
	while (p_current != NULL){
		if (p_current->data == val){
			break;
		}
		p_prev = p_current;
		p_current = p_prev->next;
	}
	//If p'current is NULL, no
	if (p_current == NULL){
		return;
	}
	
	//Delete current node: reestablish the relationship between the predecessor and successor nodes of the node to be deleted (P "current)
	p_prev->next = p_current->next;
	//Free memory of node to be deleted
	free(p_current);
}

Destroy linked list

Write function: void destroy ABCD linklist (link ABCD node * head)
Destroy the linked list and free the space of all nodes

//Destroy linked list
void destroy_linklist(link_node* head){
	if (head == NULL){
		return;
	}
	//Assignment pointer
	link_node* p_current = head;
	while (p_current != NULL){
		//Cache the next node of the current node
		link_node* p_next = p_current->next;
		free(p_current);
		p_current = p_next;
	}
}
311 original articles published, 572 praised, 500000 visitors+
His message board follow

Posted on Sat, 07 Mar 2020 19:31:14 -0800 by synchro_irl