1 of 12

DATA STRUCTURES AND ALGORITHM

Dr. Usman Ashraf

Double Linked List

2 of 12

Analysis of Singly Linked-List

we simply insert the new node after the current node. So add is a one-step operation. We just need to change two or three pointers while changing the values of some pointer variables. However, there is no need of traversing too much in the list. Incase of array, to insert an element in the center then space must be created at first then the elements should be shifted one place to right. Adjusting two to three pointers, takes less time That’s why, we can say it is a one step operation.

remove

remove is also a one-step operation

find

worst-case: may have to search the entire list

Back

moving the current pointer back one node requires traversing the list from the start until the node whose next pointer points to current node.

Moving forward in a singly-linked list is easy; moving backwards is not so easy.

3 of 12

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.

4 of 12

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

*Next

Data

5 of 12

A Singly Linked List

Head

A Doubly Linked List

6 of 12

Comparison of Linked Lists

Linked list

class Node {

int data;

Node* next;

};

Doubly linked list

class Node {

Node *previous;

int data;

Node *next;

public:

Node *getPrevious() {

return previous; };

void setPrevious(Node *prev)

{ this->previous= prev; };

};

7 of 12

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.

9 of 12

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

10 of 12