Linked List — Singly

4 min readSep 4, 2021

I’m just trying to share my thoughts and understanding of the Singly Linked List. I took all this content from Wikipedia, Geeks for Geeks and some other’s medium articles. Basically, I’m wrapping all this content in my own preferred order/format. I believe that this article will help you to get a basic idea of Singly Linked List and which may be used to recall the concepts while preparing for interviews.

Linked List

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers

In simple words, a linked list consists of nodes where each node contains a data field and a reference (link) to the next node in the list.

Why Linked List?

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

The size of the arrays is fixed.
Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create a room existing elements have to be shifted — Especially when we are inserting a new element in a sorted array.

Advantages over arrays

Dynamic size
Ease of insertion/deletion

Drawbacks

Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists efficiently with its default implementation. Read about it here.
Extra memory space for a pointer is required with each element of the list.
Not cache-friendly. Since array elements are contiguous locations, there is locality of reference which is not there in the case of linked lists.

Representation

class LinkedList {
    Node head;

    /* Linked list Node*/
    class Node {
        int data;
        Node next;

        Node(int d) { data = d; }
    }
}

Create Operation

Time complexity is O(1)
Space complexity is O(1)

class LinkedList {
    Node head; // head of list
    
    static class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    public static void main(String[] args)
    {
        LinkedList linkedList = new LinkedList();

        linkedList.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        linkedList.head.next = second;
        second.next = third;
    }
}

Read Operation

public void printList()
{
    Node n = head;
    while (n != null) {
        System.out.print(n.data + " ");
        n = n.next;
    }
}

Inserting a node

A node can be added in three ways

At the front of the linked list
After a given node.
A t the end of the linked list.

Insert — At the front of the linked list

Time complexity is O(1)
Space complexity is O(1)

public void push(int newData)
{
    Node newNode = new Node(newData);
    newNode.next = head;
    head = newNode;
}

Insert — After a given node

Time complexity is O(1)
Space complexity is O(1)

public void insertAfter(Node prev, int newData)
{
    if (prev == null)
       return;
    
    Node newNode = new Node(newData);
    newNode.next = prev.next;
    prev.next = newNode;
}

Insert — At the end

Since a Linked List is typically represented by the head of it, we have to traverse the list till the end and then change the next of last node to the new node.

Time complexity is O(n) — can be optimized to O(1) by keeping an extra pointer to the tail of a linked list.
Space complexity is O(1)

public void append(int newData)
{
    Node newNode = new Node(newData);
    newNode.next = null;    if (head == null)
    {
        head = newNode;
        return;
    }
    
    Node last = head;
    while (last.next != null) {
        last = last.next;
    }
    last.next = newNode;
    return;
}

Deleting a Linked List

In Java and Python, automatic garbage collection happens, so deleting a linked list is easy. Just need to change head to null.

Deleting a node

Time complexity is O(n)
Space complexity is O(1)

Delete the first occurrence of the key in the linked list

void deleteNode(int key)
{
    Node temp = head, prev = null;
 
    // If head node itself holds the key to be deleted
    if (temp != null && temp.data == key) {
        head = temp.next; // Changed head
            return;
    }
 
    while (temp != null && temp.data != key) {
        prev = temp;
        temp = temp.next;
    }
 
    // If key was not present in linked list
    if (temp == null)
        return;
 
    prev.next = temp.next;
}

Delete a linked list node at the given position

void deleteNode(int position)
{
    if (head == null)
        return;
        
    Node temp = head;
  
    if (position == 0) {
        head = temp.next;
        return;
    }
  
    for (int i=0; temp!=null && i<position-1; i++)
        temp = temp.next;
  
    if (temp == null || temp.next == null)
        return;
        
    Node next = temp.next.next;
    temp.next = next;
}

Length of a Linked List

Time complexity is O(n)
Space complexity is O(1)

public int getCount()
{
    Node temp = head;
    int count = 0;
    while (temp != null)
    {
        count++;
        temp = temp.next;
    }
    return count;
}

Thanks…

I Am…..

I am a Software Engineer having experience in mobile app development with expertise in Java, Android and Flutter. Interested people can contact me through LinkedIn and Instagram.

My References

Geeks For Geeks