Linked List

Linked List

As we know that Array is very useful data structure but it has certain limitations:

  1. changing the size of the array requires creating a new array and then copying all data from the array with the old size to the array with the new size and
  2. the data in the array are next to each other sequentially in memory, which means that inserting or deleting an item inside the array requires shifting some other data in this array.

This limitation can be overcome by using linked structures. Linked lists is a simple data structure which contains individual elements(say nodes) with links between them and the nodes are arranged in a linear order. Each node in a linked list contains a reference (or link) to the next node. As compared to Array, Linked List has some advantage- Linked list is unbounded, deletion of an element is faster because only you have to change some links, there is no shifting of elements. You can use a linked list in many cases in which you use an array, unless you need frequent random access to individual items using an index.

Types of Linked List

  • Singly Linked List: If a node has a link only to its successor in a Linked List, then the list is called a singly linked list. A node includes two data fields: info and next. The info field is used to store information, and this field is important to the application. The next field is used to link together nodes to form a linked list. Last node point to null.
    Singly Linked List
  • Java implementation of Singly Linked List

    Create a Node class first which will keep info and link to the next element.

    Create LinkList class which will hold nodes.

    Let’s understand each methods in detail.
    insertFirst(): This method insert a new node at the beginning of the list. This is very simple – create a new Node to insert and points its next to the old first, now you have new Node at the start so make it first. Using insert first you can create a Stack. It take O(1) time.
    Singly Linked List-insert
    insertLast(): This method insert a new node at the end of the list. You traverse the whole list to reach at the last position. Point the next pointer of last to the new Node. It takes O(n) time where n is the current size of the list.
    Singly Linked List-insertlast
    delete(): Delete the Node of given value. If the first Node contain the value then just move first to the next element of first else traverse the list to find the Node, maintain current and previous pointer where previous will point to the previous Node of current. After finding node just point previous->next to current->next. In worst case it will take O(n) time where the element is at the last position or there is no such element in list.
    Singly Linked List-delete
    find(): This method traverse the list and match each Node value to the given value, if match is found it return the Node. In worst case it will take O(n) time where the element is at the last position or there is no such element in list.

    Go to the next page – Click on the below red circle with page number.