A linked list is a list of nodes. Each node contains a value and a reference to the next node in the list.
4
0x1532
51
0x156
7
We often use a head variable to keep track of the address of the first node in the linked list.
0x1234
4
0x1532
51
0x156
7
Due to its structure, it is slower than an array for accessing elements, but faster for inserting and deleting elements.
We want to access the 2nd node in the linked list, which contains the value 51. You check the address of the head, which is a variable that contain the address of the first node in the linked list.
0x1234
4
0x1532
51
0x156
7
You can then access the first node, which contains the value 4, and then follow the pointer to the next node.
0x1234
4
0x1532
51
0x156
7
You can now access the second node, which contains the value 51.
0x1234
4
0x1532
51
0x156
7
We want to insert a new node with the value 23 at the 2nd position in the linked list.
0x1234
4
0x1532
51
0x156
7
We create a new node with the value 23.
23
We want to insert the new node after the first node, which contains the value 4. We need to update the pointer of the first node to point to the new node, and the pointer of the new node to point to the second node, which contains the value 51.
0x1234
4
0x1532
23
0x157
51
0x156
7
We want to remove the 2nd node in the linked list, which contains the value 51.
0x1234
4
0x1532
51
0x156
7
We can access the first node, which contains the value 4, and then follow the pointer to the second node. we update the pointer of the first node to point to the third node, which contains the value 7.
0x1234
4
0x1532
7
The second node, which contained the value 51, is now removed from the linked list. We don't forget to free the memory allocated for the removed node to avoid memory leaks !
Simple linked list is a linked list that only contains a reference to the next node in the list.
0x1234
4
0x1532
51
0x156
7
Doubly linked list is a linked list that contains a reference to both the next and previous nodes in the list.
0x1234
4
0x1532
0x1234
51
0x156
0x1532
7
Circular linked list is a linked list where the last node points to the first node, creating a circular structure.
0x1234
4
0x1532
51
0x156
4
0x1234
12
0x567