More

    LINKED LIST – BASIC CONCEPTS AND OPERATIONS

    A Linked List is a collection of elements linked together. Each element in a linked list is called a Node. Each Node has a reference to the next node apart from the data that it holds. Usually the first node is called Head and last node is called Tail.

    Linked List ADT

    The data, link and the following operations make linked list an ADT:

    • Insert
    • Delete
    • Count (or length)
    • Search

    The Linked List Node

    A simple linked list node can be shown as:

    class Node{

      int data;

      Node next;

    }

    In real world you will have complex data or may use a generic type for data, if the programming language support it (e.g. generics in Java).

    SINGLY LINKED LISTS

    Each element will have a pointer (or link) to the next element in the list. The link of the last node will be null, which indicates end of the list.

    Steps for traversing the linked list (and printing the element data)

    1. Follow the pointers.
    2. Display the contents of the nodes.
    3. Stop when next pointer points to null.

    Note: To count the number of elements, you can use a counter variable and incrementing it while traversing.

    INSERTION INTO A SINGLY LINKED LIST

    We can insert an element either at the beginning, at the end or in middle.

    Steps for inserting at the beginning

    1. Update the next pointer of the new node to the current head.
    2. Update the head pointer to point to the new node.

    Steps for inserting at the end

    1. New node’s next pointer is set to null.
    2. Traverse till the last node if we are not using a tail pointer.
    3. Last node’s next pointer points to the new node.

    Steps for inserting at middle (nth location)

    1. Traverse till (n-1)th location and assign it as position.
    2. Now nodes next pointer points to positions next pointer.
    3. Position nodes next pointer points to new node.

    Notes:

    1.  Need to check that the location n is not greater than size+1.
    2. This will also work even if n is added to the end, but will have to adjust tail (if available) accordingly.
    3. Insertion at the end and inserting at arbitrary location are common list operations.

    DELETION

    Deleting first node

    1. Create a temporary node that point to head
    2. Make the head points to point to next node
    3. Dispose (and return) temp node

    Deleting the last node

    1. Traverse the list and while traversing maintain previous node as well.
    2. Update the previous nodes next to null.
    3. Dispose the tail node.

    Deleting an intermediate node

    1. Traverse the list maintaining a previous node as well.
    2.  Change the previous nodes next pointer to the next node of the node to be deleted.
    3. Dispose the current node to be deleted.

    The deletion of last node and intermediate node can be combined by changing previous nodes next pointer to node-to-be-deleted’s next. If current is the last element assigning its next to previous next means assigning null to previous next. We can do this deletion without using a separate previous pointer.

    DOUBLY LINKED LIST

    Doubly linked list is a linked list which has two links: one that point to the previous element and one that point to the next element.

    Recent Articles

    OAUTH – FREQUENTLY ASKED QUESTIONS FOR INTERVIEWS AND SELF EVALUATION

    Why is refresh token needed when you have access token? Access tokens are usually short-lived and refresh tokens are...

    SUMO LOGIC VIDEOS AND TUTORIALS

    Sumo Logic Basics - Part 1 of 2 (link is external) (Sep 29, 2016)Sumo Logic Basics - Part 2 of 2...

    GIT – USEFUL COMMANDS

    Discard all local changes, but save them for possible re-use later:  git stash Discarding local changes...

    DISTRIBUTED COMPUTING – RECORDED LECTURES (BITS)

    Module 1 - INTRODUCTION Recorded Lecture - 1.1 Introduction Part I – Definition

    BOOK REVIEW GUIDELINES FOR COOKBOOKS

    Whenever you add reviews for the book, please follow below rules. Write issues in an excel.Create an excel...

    Related Stories

    Leave A Reply

    Please enter your comment!
    Please enter your name here

    Stay on op - Ge the daily news in your inbox