Skip to content

#3 Linked Lists

similar to array linked list is also a linear data structure. Each element in the linked list is actually a separate object while all the objects are linked together by the reference field in each element.

There are 2 types of linked lists the above one is called a singly-linked list and the below one is called a doubly-linked list.

Unlike the array, we are not able to access a random element in a singly-linked list in Constant Time O(1) instead we would need to transverse through the list in O(N) time to find our value at a particular location

Insertion

Unlike array adding a new Node to the list will take only O(1) time because we needn’t shift the list as we did in the array. Also, we can insert the node in the list with O(1) complexity.

It supports insertion on new nodes anywhere within the linked list.

Deletion

Deleting a node from the linked list is done in O(n) complexity because we would need to transverse to the location where we want to remove a node.

Node Creation

// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

Linked List

class MyLinkedList {
    private SinglyListNode head;
    /** Initialize your data structure here. */
    public MyLinkedList() {
        head = null;
    }
}

Helper methods

/** Helper function to return the index-th node in the linked list. */
private SinglyListNode getNode(int index) {
    SinglyListNode cur = head;
    for (int i = 0; i < index && cur != null; ++i) {
        cur = cur.next;
    }
    return cur;
}
/** Helper function to return the last node in the linked list. */
private SinglyListNode getTail() {
    SinglyListNode cur = head;
    while (cur != null && cur.next != null) {
        cur = cur.next;
    }
    return cur;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
    SinglyListNode cur = getNode(index);
    return cur == null ? -1 : cur.val;
}

Add Nodes:

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
    SinglyListNode cur = new SinglyListNode(val);
    cur.next = head;
    head = cur;
    return;
}

/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
    if (head == null) {
        addAtHead(val);
        return;
    }
    SinglyListNode prev = getTail();
    SinglyListNode cur = new SinglyListNode(val);
    prev.next = cur;
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
    if (index == 0) {
        addAtHead(val);
        return;
    }
    SinglyListNode prev = getNode(index - 1);
    if (prev == null) {
        return;
    }
    SinglyListNode cur = new SinglyListNode(val);
    SinglyListNode next = prev.next;
    cur.next = next;
    prev.next = cur;
}

Delete Nodes:

/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
    SinglyListNode cur = getNode(index);
    if (cur == null) {
        return;
    }
    SinglyListNode prev = getNode(index - 1);
    SinglyListNode next = cur.next;
    if (prev != null) {
        prev.next = next;
    } else {
        // modify head when deleting the first node.
        head = next;
    }
}

Linked List Cycle:

When we have to find whether a LinkedList is a cyclic linked list it’s always better to use 2 pointer technique to resolve the solution. Here if one pointer is moving twice the distance as the other than in the cycle both pointers are destined to intersect

Double Linked List

Similar to single linked list double linked list has one more reference field known as “prev” field. Because of which we could easily tell the previous node.

traversal of linked list becomes easy, while write operation complexity is increased due to added field

 // Definition for doubly-linked list.
class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) {val = x;}
}

Comparison of time complexity b/w array and Linked List

So if we want to add/delete data frequently a linked list is a good choice.

If you need to access a element at a index frequently array would be a better choice else linked list.

Published inData Structures

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *