Basic knowledge of linked list

Type of linked list

What is a linked list , A linked list is a linear structure connected in series by pointers , Each node is made up of two parts , One is the data field and the other is the pointer field （ Holds a pointer to the next node ）, The pointer field of the last node points to null（ A null pointer means ）.
The entry point of the link is called the head node of the list, which is head.

Type of linked list

Single chain list

Just now

Double linked list

A node in a single linked list can only point to the next node of a node .

Double linked list ： Each node has two pointer fields , One points to the next node , One points to the previous node .

Double linked list You can query forward or backward .

Circular linked list

Circular linked list , seeing the name of a thing one thinks of its function , The linked list is connected end to end .

Circular linked list can be used to solve Joseph ring problem .

storage

Arrays are continuously distributed in memory , But linked lists are not continuously distributed in memory .

The linked list links the nodes in the memory through the pointer of the pointer field .

So the nodes in the linked list are not continuously distributed in memory , It's scattered on some address in memory , The allocation mechanism depends on the memory management of the operating system .
As shown in the figure, the starting node of this linked list is 2, The termination node is 7, Each node is distributed in a different memory address space , Connected in series by a pointer .

Code —— Definition of linked list

// Single chain list 
struct ListNode{
    
	int val;// Data stored on the node 
	ListNode *next;// Pointer to the next node 
	ListNode(int x):val(x),next(NULL){
    }// Constructors  
}; 

It's OK without this constructor ,c++ A constructor will be generated by default .
But this constructor does not initialize any member changes , Two examples ：

Initialize the node by defining its own constructor ：
ListNode* head = new ListNode(5);

Use the default constructor to initialize the node
ListNode* head = new ListNode(); head->val = 5;

So if you don't define a constructor and use the default constructor , You can't assign values to variables directly during initialization ！

Operation of linked list

Delete node

As long as C Node next The pointer Point to E Node is OK .

That's what some students said ,D Nodes are still in memory ？ It's just not in this list .

That's true , So in C++ It's better to release this manually D node , Free up this memory .（free）

Other languages such as Java、Python, It has its own memory recovery mechanism , You don't have to release it yourself .

Add node

It can be seen that the addition and deletion of linked list are O(1) operation , And it doesn't affect other nodes .

But be careful , If you delete the fifth node , You need to find the fourth node from the beginning through next Pointer to delete , The time complexity of the search is O(n).

Performance analysis

Note the insertion of the linked list / The deletion time complexity is O(1) Because the previous node is known , If you simply delete a specific element from a linked list , So you need to traverse + Delete , Time complexity is O(n) 了 .

When an array is defined , The length is fixed , If you want to change the length of the array , You need to redefine a new array .

The length of the linked list can be unfixed , And it can be added and deleted dynamically , Suitable for data volume is not fixed , Add and delete frequently , Less query scenarios .