• LinkedIn
  • Facebook
  • YouTube
  • Twitter
  • Instagram
  • Pinterest
  • Tumblr

Singly Linked List - Everything You Need To Know

Updated: Apr 9

Introduction


Linked list is a linear data structure. Each element in a linked list is an individual object. These individual objects are called nodes. As the name suggests a linked list is formed by interconnecting a series of such nodes. Nodes are connected using pointers.


Each node internally contains data and a link to the next node (address of the next node). In general a node in a linked list appears as shown in figure below:


The first node in a linked list is called a head node. The head node is the entry point to a linked list. Unlike arrays linked list elements are not indexed, we cannot access any random element using an index like arrays. We always start traversing the linked list from the head node no matter which element we need to access in the list.


The last node in a linked list is not connected to any node. The next pointer of the last node always points to null.


Linked list can contain any type of data like int, string, character etc. Elements can all be unique or it can also contain duplicates. Also the elements in a linked list can be sorted or unsorted.


Unlike arrays elements in a linked list are not stored in contiguous locations in memory. Each node is stored in arbitrary location in memory and connected to each other using next pointer.


Why Linked List?


  1. Arrays are fixed size structures. Once an array is declared you cannot change its size. If the array is full and a new element needs to be added, you need to declare a new array (of larger size) and copy all the elements from the old array into the new array. This can be an expensive operation especially for large arrays. Linked list unlike arrays are dynamic in nature, they do not have a fixed size. We just a have to create a new node and link it to our list each time a new element needs to be added.

  2. Another scenario where a linked list is useful is when you do not know the size of input beforehand, declaring a large array to accommodate such an input is a waste of memory. For such use cases linked list is useful because you need not specify the size while declaring a linked lists.

  3. Linked lists (especially doubly linked list) are often used because of their efficient insert and delete operations.

  4. Linked list allows you to efficiently add a new node between existing nodes in a list. This cannot be efficiently done in case of arrays. If a new element is to be added in between existing elements in arrays, you need to shift all the other elements to make space for the new element.


Linked List Drawbacks


  1. Unlike arrays linked lists do not support indexing. To find nth element in a linked list we have the traverse the list from first node till nth node.

  2. Linked lists use comparatively more space than arrays since each node needs to store a link to the next or previous node in addition to storing the actual data.

  3. Arrays have a good locality of reference since the elements are stored in contiguous location in memory. But linked list nodes are placed in arbitrary locations in memory. As a result CPU can't efficiently cache linked lists like arrays.


Linked List vs Arrays


  1. Arrays give you the ability to access elements in O(1) time. In linked lists you start the traversal from the first element, so the worst case time complexity for search an element in linked list is O(n).

  2. Arrays have fixed size. Linked lists have no size constraints, any number of new elements can be added to a linked list (as long as you have memory).

  3. Since linked list nodes need to store pointer to the next node in the list, they comparatively take more space as compared to arrays.

  4. Linked lists give you the flexibility to easily add and remove elements from the middle (between any nodes) as compared to arrays where you will have to shift all other elements in order to achieve this.

  5. Unlike arrays, elements in a linked list are not stored at contiguous location in memory. Elements are connected using pointers.


Types Of Linked List


Depending on how the nodes are connected there are various types of linked lists:

  1. Singly linked list

  2. Doubly linked list

  3. Circular linked list

In this article we will discuss about singly linked list. We will cover doubly and circular linked lists in detail in a separate article.


Singly Linked List


A singly linked list is formed by connecting nodes using a single link between them. This single link is formed using the next pointer of the node. A singly linked list looks as shown in figure below:


To implement singly linked list we need to define two structures, one for the node and one for the linked list itself.


Lets define the structure for linked list first:

type LinkedList struct {
   head *Node
}

The LinkedList structure has one field head which is a pointer to head node (address of the head node). As stated earlier a head node is an entry point to a linked list. So when a linked list is first created we store the address of the head node in this field and we always start traversing the linked list from the head node using the address defined in head.


Next lets define the linked list node:

type Node struct {
   data int
   next *Node
}

Node structure contains two fields: data which represents the node data (for simplicity lets assume it is of int type) and next which is a pointer to the next node in the list.


In an object oriented language like Java, Python we use Class instead of struct to represent the linked list.


Linked List Class

Node Class


Inserting A Node


Usually we insert new data at the end of the linked list. But there are cases where we may have to insert at head, insert after a specified node, insert before a specified node or insert at a specific position in the given linked list.


Insert At The End


To insert an element at the end of singly linked list we need to do the following steps:

  1. Take a temporary node pointer. We need to move this pointer from start of the list to end. Lets call this temporary node as currentNode. At the beginning currentNode points to the head node.

  2. Keep moving the currentNode pointer until it reaches the last node.

  3. Once the currentNode reaches the last node in the list, make the next pointer of the last node to point to the new node to be added i.e. currentNode.next = newNode.


Implementation


Language: Go


Language: Java


Insert Before A Node


To insert a new node before a certain node, traverse the list until the node just before the specified node, then point the next of current node to the new node and next of new node to the before node.


To insert a new node before a certain node in a singly linked list we need to do the following steps:

  1. Let beforeNode be the node before which we have to insert the new node and let the new node to be inserted be called newNode.

  2. Take a temporary node pointer. Lets call this temporary node as currentNode. To begin with currentNode points to the head node.

  3. Move the currentNode pointer from start of the list until the node just before the beforeNode.

  4. Now connect the next of currentNode to newNode and next of newNode to the previous next of currentNode.


Lets understand this with an example. Consider you are given the below linked list:


Lets say we have to add a new node with data = 3 before node 4( with data = 4). First we need to traverse the list from head the head node until node 2 (node before beforeNode). Once we reach node 2 we break the link between node 2 and 4 as show in figure below:


Then we connect the next of node 2 to node 3 (new node). After that we connect the next of node 3 to node 4 as shown in figure below:

As you can see in above figure node 3 is now inserted in the list before node 4.


Implementation


Language: Go


Language: Java



Insert After A Node


Similarly to insert a new node after a specified node we have to traverse the list from head node until the afterNode. After that, we need to point the next of the afterNode to the newNode and next of newNode to the node previously pointed to by the afterNode.


Lets understand this with an example. If we were given the below linked list and we had to insert a new node with data = 3 after node with data=2:



We traverse the list from head node to until node 2. Then point next of node 2 to newNode and next of newNode to node 4.

Implementation


Language: Go


Language: Java