Two- Way List & Its Operations

Two Way Lists:

Two way lists is a linear collection of data elements, called nodes, where each node N is divided into three parts:

1. An information field INFO which contains data of node N.
2. A pointer field FORW which contains the location of the next node in the list.
3. A pointer Field BACK which contain the location of the preceding node in the list

The list also requires a pointer variable: FIRST, which points to the first node in the list, and LAST, which points to the last node in the list shown in figure.  Observe that NULL pointer appears in FORW field of the last node in the list and also in BACK field of the first node in the list:

Observe that using the variable FIRST and the pointer field FORW, we can traverse into a list in forward direction.  On the other hand using the variable LAST and pointer variable BACK we can also traverse the list in backward direction 

Suppose LOCA and LOCB are the locations, respectively, of node A and B in a two way list.  Then the way that the pointer FORW and BACK are define given us the following:

Pointer property: FORW [LOCA] = LOCB if and only if BACK [LOCB]:=LOCA

Deleting a node in Two-Way List:

Suppose we are given the location LOC of node N in LIST and suppose you want to delete N from the list. N is deleted from the list by changing the following pair of pointers.

FORW[BACK[LOC]]:= FORW[LOC] and BACK[FORW[LOC]]:=BACK[LOC]

  The deleted N is then returned to AVAIL list by the assignment:

                     FORW [LOC]:=AVAIL             and      AVAIL:=LOC

Algorithm: DELTWL (INFO, FORW, BACK, START, AVAIL, LOC)

1. [Delete node.]

            Set FORW [BACK [LOC]]:= FORW[LOC] and 

                BACK [FORW [LOC]]:=BACK[LOC]

         2.  [Return node to AVAIL list]

            Set FORW[LOC]:=AVAIL and AVAIL:=LOC

     3. Exit

Inserting a node in Two-Way List:

Suppose we are given the location LOCA and LOCB of adjacent nodes A and B in the list, and suppose we want to insert a given ITEM of information between nodes A node B.  As with a one way list, first we remove the first node N from the AVAIL list,  using the variable new to keep track of its location,  and then we copy the data ITEM into the node N,  we set:

 NEW: = AVAIL,         AVAIL: =FORW[AVAIL],      INFO[NEW]:=ITEM

 Now the node N with the content ITEM is inserted into the list by changing the following pair of pointers: 

                FORW[LOCA]:=NEW ,                   FORW[NEW]:=LOCB

                BACK[LOCB]:=NEW ,                  BACK[NEW]:=LOCA

Algorithm: INSTWL (INFO, FORW, BACK, START, AVAIL, LOCA, LOCB, ITEM)

1. [OVERFLOW?] If AVAIL=NULL, then: Write: OVERFLOW, and Exit

2.[Remove the node from list and copy new data into node

        Set NEW:= AVAIL,   AVAIL:=FORW[AVAIL],       INFO[NEW]

3.[Insert node into list]

        Set FORW[LOCA]:=NEW ,             FORW[NEW]:=LOCB

  BACK[LOCB]:=NEW ,              BACK[NEW]:=LOCA