Singly Linked List - Everything You Need To Know

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

Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

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

Deleting A Node

Deleting a node from a linked list is straight forward. We need to check if the given node is present in the list. If present remove it from the list and return the deleted node. Else return null.

Language: Java

Get All Elements

To get a list of all elements present in a linked list we need to traverse the list from the head node to the last node and return the values present.

Implementation

Language: Go

Complexity Analysis

Time Complexity

Search : O(n)

Worst case time complexity for search operation is O(n) as we may end up checking each node to find an element in the worst case. Worst case time complexity occurs when the node to be searched is the last node in the list or if the given node is not present in the list.

Insert: O(n)

Insert operation also has a worst case of O(n) as we have to go through all the nodes before inserting the new node similar to search operation.

Delete: O(n)

Worst case complexity of delete is also O(n).

Space Complexity: O(n)

Each node in a linked list needs to store link to the next node along with the actual data. This means the space needed increases linearly for each new node added. Therefore, space complexity for a singly linked list is O(n).

Now you know what a singly linked list is and how to implement it. Do not stop here, deepen your knowledge by exploring more articles on linked lists.

That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.

If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).

You can explore more such amazing articles from code recipe here.

Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time: Join now

Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.