Scribd Logo
Upload

Welcome to Scribd!

  • 54 views

    Lecture 3 - Doubly Linked List

    Uploaded by

    M I Malik
    This document discusses doubly linked lists. A doubly linked list contains nodes that have two pointers - one to the next node and one to the previous node, allowing bidirectional traversal of the list. This overcomes the limitation of singly linked lists which only allow forward traversal. The document compares singly and doubly linked lists, and covers insertion and deletion operations in doubly linked lists which require updating both the predecessor and successor pointers. Advantages of doubly linked lists include bidirectional traversal and ability to search predecessors/successors quickly, while disadvantages are increased memory usage and processing time for some operations.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lecture 3 - Doubly Linked List

    Uploaded by

    M I Malik
    54 views11 pages
    This document discusses doubly linked lists. A doubly linked list contains nodes that have two pointers - one to the next node and one to the previous node, allowing bidirectional traversal of the list. This overcomes the limitation of singly linked lists which only allow forward traversal. The document compares singly and doubly linked lists, and covers insertion and deletion operations in doubly linked lists which require updating both the predecessor and successor pointers. Advantages of doubly linked lists include bidirectional traversal and ability to search predecessors/successors quickly, while disadvantages are increased memory usage and processing time for some operations.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses doubly linked lists. A doubly linked list contains nodes that have two pointers - one to the next node and one to the previous node, allowing bidirectional traversal of the list. This overcomes the limitation of singly linked lists which only allow forward traversal. The document compares singly and doubly linked lists, and covers insertion and deletion operations in doubly linked lists which require updating both the predecessor and successor pointers. Advantages of doubly linked lists include bidirectional traversal and ability to search predecessors/successors quickly, while disadvantages are increased memory usage and processing time for some operations.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    54 views11 pages

    Lecture 3 - Doubly Linked List

    Uploaded by

    M I Malik
    This document discusses doubly linked lists. A doubly linked list contains nodes that have two pointers - one to the next node and one to the previous node, allowing bidirectional traversal of the list. This overcomes the limitation of singly linked lists which only allow forward traversal. The document compares singly and doubly linked lists, and covers insertion and deletion operations in doubly linked lists which require updating both the predecessor and successor pointers. Advantages of doubly linked lists include bidirectional traversal and ability to search predecessors/successors quickly, while disadvantages are increased memory usage and processing time for some operations.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 11

    Data Structures & Algorithms

    Lecture 3

    Doubly Linked List

    Computer Science
    Introduction
    • The singly linked list contains only one pointer
    field i.e. every node holds an address of next
    node.

    • The singly linked list is uni-directional i.e. we can


    only move from one node to its successor.

    • This limitation can be overcome by Doubly


    linked list.

    Computer Science
    Doubly Linked List
    • In Doubly linked list, each node has two
    pointers.
    • One pointer to its successor (NULL if there is
    none) and one pointer to its predecessor (NULL
    if there is none).
    • These pointers enable bi-directional traversing .

    *Previous Data *Next

    Computer Science
    A Singly Linked List
    Head

    A Doubly Linked List

    Head

    Computer Science
    Comparison of Linked Lists
    • Linked list
    struct Node {
    int data;
    Node* next;
    };
    • Doubly linked list
    struct Node {
    Node *previous;
    int data;
    Node *next;
    };
    Computer Science
    Insertion
    • In insertion process, element can be inserted in three
    different places
    – At the beginning of the list
    – At the end of the list
    – At the specified position.

    • To insert a node in doubly linked list, you must update


    pointers in both predecessor and successor nodes.

    Computer Science
    Insertion

    Computer Science
    Deletion
    • In deletion process, element can be deleted from three
    different places
    – From the beginning of the list
    – From the end of the list
    – From the specified position in the list.

    • When the node is deleted, the memory allocated to that


    node is released and the previous and next nodes of that
    node are linked

    Computer Science
    Deletion

    Computer Science
    Advantages of Doubly Linked List

    1. The doubly linked list is bi-directional, i.e. it can be


    traversed in both backward and forward direction.
    2. The operations such as insertion, deletion and
    searching can be done from both ends.
    3. Predecessor and successor of any element can be
    searched quickly

    Computer Science
    Disadvantages

    1. It consume more memory space.


    2. There is a large pointer adjustment during insertion and
    deletion of element.
    3. It consumes more time for few basic list operations.

    Computer Science

    You might also like