Doubly Linked List in Data Structure

A doubly linked list contains two pointers on each node: One will point the previous node and the other will point the next node.

Advantage of Doubly Linked List:

This helps to traverse the list in forward & backward direction.

Insertion of node in doubly linked list:

A. Insertion of node at the beginning

Algorithm: INSBEG (START, INFO, PREV, NEXT, ITEM, TEMP)

This algorithm inserts TEMP as first node in the doubly linked list. ITEM variable contains data of new node.

Step 1: Allocate memory for new node TEMP.

Step 2: [ Store the ITEM into INFO part of new node ]

TEMP →  INFO := ITEM

Step 3: [ Insert the new node TEMP as first node. ]

TEMP  →  NEXT := START

START := TEMP

TEMP  →  PREV := NULL

If START ≠ NULL then             [ List is not empty ]

START  →  PREV := TEMP

[ End of If structure ]

Step 4: [ Exit ]

Return.

B. Insertion of node at the end

Algorithm: INSLAST (START, INFO, NEXT, PREV, ITEM, TEMP, PTR)

This algorithm inserts TEMP as last node in the linked list. ITEM variable contains data of new node.

Step 1: Allocate memory for new node TEMP.

Step 2: [ Store the ITEM into INFO part of new node ]

TEMP  →  INFO := ITEM

Step 3: [ Make the TEMP node points to NULL. ]

TEMP  →  NEXT := NULL

Step 4: [Check whether list is empty or not. ]

If START = NULL then

TEMP  →  PREV := NULL

START := TEMP

and Return.

[ End of If structure ]

Step 5: [ Initialize the PTR variable. ]

PTR := START

Step 6: [ Increment the PTR variable ]

Repeat while PTR  →  NEXT ≠ NULL

PTR := PTR  →  NEXT

[ End of Loop structure ]

Step 7: [ Insert the new node TEMP as last node. ]

PTR →  NEXT := TEMP

TEMP  →  PREV := PTR

Step 8: [ Exit ]

Return.

C. Insertion of node after specified position

Algorithm: INST (START, INFO, PREV, NEXT, ITEM, TEMP, POS, C, PTR, Q)

This algorithm inserts TEMP node after position POS in the doubly linked list. ITEM variable contains data of new node.

Step 1: [ Check whether list is empty or not. ]

If START = NULL then

Write (‘List is empty’)

and return.

[ End of If structure ]

Step 2: [ Initialize the PTR and C variable. ]

PTR := START

C := 0

Step 3: Repeat while PTR ≠ NULL AND C ≠ POS

C := C+1

Q := PTR

PTR := PTR  →  NEXT

[ End of Loop structure ]

Step 4: If PTR = NULL and C ≠ POS then

Write (‘Position not found’) and Return.

Step 5: Allocate memory for new node TEMP.

Step 6: [ Store the ITEM into INFO part of new node ]

TEMP  →  INFO := ITEM

Step 7: [ Insert the new node TEMP. ]

TEMP  →  NEXT := PTR

PTR  →  PREV := TEMP

Q  →  NEXT := TEMP

TEMP  →  PREV := Q

Step 8: [ Exit ]

Return.

Deletion of node from linked list:

A. Deletion of first node

Algorithm: DELBEG (START, INFO, NEXT, PREV, ITEM, TEMP)

This algorithm deletes the first node from the doubly linked list and store it in TEMP. ITEM variable is used to store the data of deleted node.

Step 1: [Check whether list is empty or not. ]

If START = NULL then

Write (‘List is empty’) and return.

[ End of If structure ]

Step 2: [ Store the data of first node into ITEM. ]

ITEM := START  →  INFO

Step 3: [ Remove the node ]

TEMP := START

START := START  →  NEXT

START  →  PREV := NULL

Step 4: Free the TEMP node.

Step 5: [ Exit ]

Return.

B. Deletion of Last Node

Algorithm: DELLAST (START, INFO, NEXT, PREV, ITEM, PTR, Q)

This algorithm deletes the last node from the doubly linked list. ITEM variable is used to store the data of deleted node.

Step 1: [Check whether list is empty or not. ]

If START = NULL then

Write (‘List is empty’) and return.

[ End of If structure ]

Step 2: [ Initialize the PTR variable. ]

PTR := START

Step 3: Repeat while PTR  NEXT ≠ NULL

Q := PTR

PTR := PTR  →  NEXT

[ End of Loop structure ]

Step 4: [ Store the data of last node into ITEM. ]

ITEM := PTR  →  INFO

Step 5: [ Deletes the node ]

Q  →  NEXT := NULL

Step 6: Free the PTR node.

Step 7: [ Exit ]

Return.

C. Deletion of node containing particular data

Algorithm: DELETE (START, INFO, NEXT, PREV, ITEM, PTR, Q)

This algorithm deletes the node containing the data ITEM from the doubly linked list.

Step 1: [Check whether list is empty or not. ]

If START = NULL then

Write (‘List is empty’) and return.

[ End of If structure ]

Step 2: [ Initialize the PTR variable. ]

PTR := START

Step 3: Repeat while PTR ≠ NULL

If PTR  →  INFO = ITEM, then

If PTR = START, then     [ First node is to be deleted ]

START = START  NEXT

If START ≠ NULL [ There is more than one node ]

START  →  PREV := NULL

[ End of If structure ]

Else:

If PTR  →  NEXT = NULL, then           [ Data is at last node ]

Q  →  NEXT := NULL

Else:

Q  →  NEXT := PTR  →  NEXT

PTR  →  NEXT  →  PREV := Q

[ End of If structure ]

Free the PTR node and Return.

Else:

Q := PTR [ Moving to next node. ]

PTR := PTR  →  NEXT

[ End of If structure ]

Step 4: Write (‘ITEM not found’)

Step 5: [ Exit ]

Return.