Linked List

Write a program to implement singly linked list

Pinterest LinkedIn Tumblr

Linked list is a data structure consisting of a group of nodes which together represent a sequence. Each node links (memory to next item) to next node. Linked list allocate the memory on demand. Each node contains data and the link to the next node. The last node points to NULL as next link.

Linked list supports insertion, deletion and traversal operations. Insertion and deletion node operations are easily implemented in a linked list. Linked list is useful when the data insert to the list or remove from the list without re-arrange the nodes at any position. The array uses the index to access the elements. If the new element inserted in the middle of the array, the elements need to re-arrange the order. But, the linked list allows to insert in any location using the links.

The dynamic array can be used when the array needs dynamically manage the memory and access the elements using the index. The dynamic array requires more operations to copy old elements to newly created array every time (when the array need more memory). But, the linked list allocate the memory dynamically when the memory requires.

Write a program to implement singly linked list with insert, delete, and traverse operation.

Algorithm Explanation

Linked list requires Data and link for building the nodes. Each node contains data and link to the next node.
Linked list insert operation takes the data and build the node before inserting the node to linked list.
Delete operation removes the node from linked list and frees the memory.
Iteration operation iterate each element until the next node point to the null value.
Singly linked list do not support to iterate the elements from last element (reverse order). It supports only forward iteration.

Source Code

package com.dsacode.DataStructre.linkedlist;
 
public class SinglyLinkedList < E > {
 
    @SuppressWarnings("hiding")
    class Node < E > {
        E data;
        Node < E > next;
    }
 
    Node < E > start;
    int size;
 
    public SinglyLinkedList() {
        start = null;
        size = 0;
    }
 
    public void add(E data) {
        insertAtLast(data);
    }
 
    public void insertAtLast(E data) {
        if (size == 0) {
            start = new Node < E >();
            start.next = null;
            start.data = data;
        } else {
            Node < E > currentNode = getNodeAt(size - 1);
            Node < E > newNode = new Node < E >();
            newNode.data = data;
            newNode.next = null;
            currentNode.next = newNode;
        }
        size++;
    }
 
    public void insertAtFirst(E data) {
        if (size == 0) {
            start = new Node < E >();
            start.next = null;
            start.data = data;
        } else {
            Node < E > newNode = new Node < E >();
            newNode.data = data;
            newNode.next = start;
            start = newNode;
        }
        size++;
    }
 
    public Node < E > getNodeAt(int nodePos) throws ArrayIndexOutOfBoundsException {
        if (nodePos >= size || nodePos < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        Node < E > temp = start;
        int counter = 0;
        for (; counter < nodePos; counter++) {
            temp = temp.next;
        }
        return temp;
    }
 
    public void insertAt(int position, E data) {
        if (position == 0) {
            insertAtFirst(data);
        } else if (position == size - 1) {
            insertAtLast(data);
        } else {
            Node < E > tempNode = getNodeAt(position - 1);
            Node < E > newNode = new Node < E >();
            newNode.data = data;
            newNode.next = tempNode.next;
            tempNode.next = newNode;
            size++;
        }
    }
 
    public Node < E > getFirst() {
        return getNodeAt(0);
    }
 
    public Node < E > getLast() {
        return getNodeAt(size - 1);
    }
 
    public E removeAtFirst() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        E data = start.data;
        start = start.next;
        size--;
        return data;
    }
 
    public E removeAtLast() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        Node < E > tempNode = getNodeAt(size - 2);
        E data = tempNode.next.data;
        tempNode.next = null;
        size--;
        return data;
    }
 
    public E removeAt(int position) {
        if (position == 0) {
            return removeAtFirst();
        } else if (position == size - 1) {
            return removeAtLast();
        } else {
            Node < E > tempNode = getNodeAt(position - 1);
            E data = tempNode.next.data;
            tempNode.next = tempNode.next.next;
            size--;
            return data;
        }
    }
 
    public int size() {
        return size;
    }
 
    public String toString() {
        if (size == 0) {
            return "";
        } else {
            StringBuilder output = new StringBuilder();
            Node < E > tempNode = start;
            while (tempNode.next != null) {
                output.append(tempNode.data).append(", ");
                tempNode = tempNode.next;
            }
            output.append(tempNode.data);
            return output.toString();
        }
    }
 
    public static void main(String[] args) {
        SinglyLinkedList < Integer > obj = new SinglyLinkedList < Integer >();
        Integer[] array = { 12, 45, 67, 32, 99, 11, 43 };
 
        for (Integer i : array)
            obj.add(i);
 
        System.out.println("Items in the linked list:" + obj.toString());
        System.out.println("Add Items 56 in linked list");
        obj.add(56);
        System.out.println("Items in the linked list:" + obj.toString());
        System.out.println("First Item removed in linked list:"
                + obj.removeAtFirst());
        System.out.println("Items in the linked list:" + obj.toString());
        System.out.println("Last Item removed in linked list:"
                + obj.removeAtLast());
        System.out.println("Items in the linked list:" + obj.toString());
 
    }
 
}

Output

Items in the linked list:12, 45, 67, 32, 99, 11, 43
Add Items 56 in linked list
Items in the linked list:12, 45, 67, 32, 99, 11, 43, 56
First Item removed in linked list:12
Items in the linked list:45, 67, 32, 99, 11, 43, 56
Last Item removed in linked list:56
Items in the linked list:45, 67, 32, 99, 11, 43

Source Explanation

Construct the array of integers and insert each item to the linked list.
Linked list construct the node with values and link to next node. A node can be inserted into last or first in the existing linked list.
Linked list iterate the nodes and find the node for removing from the list. It unlink the nodes and free the memory.
Linked list iterate nodes from head to tail. If the item found, it returns the value. Otherwise, it returns false.

Complexity

OperationsBest CaseAverage Caseworst Case
SearchO(n)O(n)
InsertionO(1)O(1)
DeletionO(1)O(1)

Real Applications

  1. Implement stacks, queues, graphs
  2. Implement Tree
  3. Symbol table management in compiler design
  4. Separate chaining in Hash tables
  5. Implement non-binary trees.
  6. Applications that have an MRU list
  7. Cache in browser
  8. Undo functionality in software
  9. Represent a deck of cards in a game.
  10. Represent polynomials

Reference

  1. https://www.cs.usfca.edu/~galles/visualization/QueueLL.html
  2. https://www.cs.usfca.edu/~galles/visualization/StackLL.html
  3. https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list
  4. http://cslibrary.stanford.edu/103/LinkedListBasics.pdf
  5. http://cis.stvincent.edu/html/tutorials/swd/lists/lists.html

Write A Comment