Two-way or Doubly Linked Lists in Data Structures

In this article, we'll talk about two way linked list. In two way linked list we can move to previous mode easily. Because in this type of linked list a node has three parts first part contain data, second part contain address of previous node and third part contain address of next node. Two way linked list is also called doubly linked list.

Two Way or Doubly Linked List

1. Traversing from beginning of two way linked list

Algorithm: (Traversing into two-way list at beginning.)
BTRVSTW(START, PTR, INFO, FORW).

Let LIST be a Two-way list in memory. This algorithm traverses LIST, and PRINT each node of LIST.

Step I: Set PTR := START. [Initializes the pointer PTR.]

Step II: Repeat steps 3 and 4 while PTR != NULL:

Step III: PRINT: INFO[PTR].
[Print information of node.]
Step IV: Set PTR := FORW[PTR].
[PTR now points to the next forward node.]
[End of step 2 loop.]
Step V: Exit.

2. Traversing from ending of two way linked list

Algorithm: (Traversing into two-way list at ending.)
ETRVSTW(END, PTR, INFO, BACKW).

Let LIST be a two-way list in memory. This algorithm traverses LIST, and PRINT each node of LIST.

Step I: Set PTR := END. [Initializes the pointer PTR.]
Step II: Repeat steps 3 and 4 while PTR != NULL:
Step III: PRINT: INFO[PTR].
[Print information of node.]
Step IV: Set PTR := BACKW[PTR].
[PTR now points to the next backward node.]
End of step 2 loop.]
Step V: Exit.

3. Deletion in Two-way list

Algorithm: (Deletion in two-way list.)
DELTW(FORW, BACK, AVAIL, LOC).

Let LIST be a two-way list in memory. This algorithm deletes a node from two-way linked list.

Step I: [Delete node.]
Set BACK[FORW[LOC]] := BACK[LOC], and
FORW[BACK[LOC]] := FORW[LOC].
Step II: [Add this node to the AVAIL list.
Set FORW[LOC] := AVAIL, and
AVAIL := LOC.
Step III: Exit.

4. Insertion in Two-way list

Algorithm: (Insertion in two-way list.)
INSTTW(FORW, BACK, AVAIL, NEW, INFO, LINK, ITEM, LOCA, LOCB).

Let LIST be a two-way list in memory. This algorithm inserts a node from two-way linked list.

Step I: [OVERFLOW?]
If AVAIL = NULL, then: Write: OVERFLOW, and Exit.
Step II: [Remove node from AVAIL list.]
Set NEW := AVAIL, and
AVAIL := LINK[AVAIL].
Step III: [Copies new data into NEW node.]
Set INFO[NEW] := ITEM.
Step IV: [Add this node to the data list.]
(i) Set FORW[NEW] := FORW[LOCA], and FORW[LOCA] := NEW
(ii) Set BACK[NEW] := BACK[LOCB], and BACK[LOCB] := NEW
Step V: Exit.