1. Introduction
A linked list is a linear collection of elements (nodes, data,..) which are linked using the pointers. Compare with arrays, elements in the linked list do not have contiguous locations. They use pointers to connect to the next elements until reaching the “null” pointer, which means it touches the end of the linked list.
There are 2 types of linked list: Singly linked list and Doubly Linked List. The Singly is the more common one, and when people talk about the linked list, if there is no additional mention, it is usually the Singly linked list.
In this article, I talk about both types to give a general understanding of this useful data structures. I also mention some operations on linked list, especially how to reverse a linked list, with example in Go. Finally, I explain the complexity of this data structure and when you should use linked list. The full source code can be found at my Github.
2. Implement a Linked List
2.1 Singly linked list
The Singly linked list has a collection of nodes. Each node will have 2 fields:
- Data (or value) of that node
- The pointer to the next node
If the next node of node A is “null”, it means node A is the last node of the list.
The list must have the head node, which is the first node of the list. If we lose or change the head, we will lose that list or have another one.
2.2 Doubly linked list
The Doubly linked list has the same idea as the Singly, except one thing that the node in Doubly linked list has one more field — the pointer to the previous node. So each node in the Doubly has:
- Data (or value) of that node
- The pointer to the next node
- The pointer to the previous node
If the next node of node A is “null”, it means node A is the last node of the list. If the previous node of node A is “null”, it means node A is the first node of the list.
3. Operations on Linked List
We can perform some operations on linked list to get the output that we expect. In this part, I will mainly talk about the Insert and Reverse, which is the common interview questions in linked list. For other operations, you can check this great blog of Ritesh Pawar. His blog inspired me to write this blog.
3.1 Insert
Problem: Insert a value or data to a linked list at the given position.
Solution: Because linked list does not have adjacent indexes like arrays, we must traverse through the linked list by the pointer. The idea is that we traverse by the next pointer and count the given index to find the right position. Then, we insert the node with the input value and adjust the pointer of the next the previous node to connect to the inserted node.
3.2 Reverse
Problem: Reverse a given linked list
Solution: This is the common interview question. When facing this problem, the first idea I think is that we should create a new list, and then append or insert the nodes from the given list to the new one. However, that approach may not be efficient. In some cases, the given linked list may be very large, and duplicating a large piece of data can cause a big cost to memory space or space complexity. So the true answer to this problem is that we should change the pointer of each node to redirect the list. This link will give you a detailed explanation.
The full source code can be found at my Github. In my Github, I also implement the above operations on Doubly linked list, and some more detail like append, prepend and show a linked list.
4. Conclusion
4.1 When you should use linked list
Linked list has a good performance when we need to insert or delete elements. The detail can be found here.
For example: when comparing with arrays, if we want to add a element to the 0th index (append), we must re-indexing all the rest of the array, which will cost O(n) complexity. If we use linked list, we just need to change the head pointer of the list to new node, and the next of the new node will be the old head. All of that just cause O(1) complexity.
Here is some application of linked list in computer science and the real world:
- Implement stacks and queues
- Implement graph
- Previous and next page in web browser
- Music player
4.2 Take-away messages
- Linked list is a linear data structure, using pointers as the main component for connections.
- We should never lose the head of the list. (As we should never lose hope in our life 😊)
- Linked list has a good performance when it comes to insertion or deletion.
- Linked list is a good beginning when you start learning data structure and algorithm.
Hope this blog will give you some useful information and support your work.
Please do not hesitate to suggest or correct anything on this blog.
Thank you for your reading and have a nice day!
