Data Structure in Go: Linked List

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

The Singly linked list has a collection of nodes. Each node will have 2 fields:

  1. Data (or value) of that node
  2. 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 description of Singly linked 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.

The declaration of Singly 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:

  1. Data (or value) of that node
  2. The pointer to the next node
  3. 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.

The description of Doubly linked list
The declaration of Doubly linked 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.

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.

Insert in Singly linked list
Insert function in Go

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.

Reverse Singly linked list

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

The space and time complexity of 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:

  1. Implement stacks and queues
  2. Implement graph
  3. Previous and next page in web browser
  4. Music player
  • 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!

Try to be a better Software Engineer everyday.