LINKED LISTS
An algorithm to insert a node into a singly linked, null terminated ordered list. We assume that the node to be inserted is pointed to by a pointer called P. Assume that the listheader is described with the following DSECT
LISTHEAD DSECT and nodes are described with this DSECT
LHINFO DS CL12 NODE DSECT
LHLINK DS A KEY DS F
LINK DS A
DCL: S, T: pointers
S = A(LSTHEADER)
T = S->LHLINK
IF (T = NULL) Node goes into empty list
S->LHLINK=P
ELSE
IF (T->KEY GE P->KEY) Node goes first into an existing list
S->LHLINK = P
ELSE
SET FLAG ON
DO WHILE (T NE NULL AND FLAG ON) Search list for location
IF (T->KEY GE P->KEY)
SET FLAG OFF
ELSE
S=T
T=T->LINK
ENDIF
ENDDO S now points to node after which we want to insert new node
S->LINK=P
ENDIF
ENDIF
P->LINK = T
An algorithm to delete a node from an ordered, singly linked, null terminated list. We assume that the key to search for is contained in a word called DLTKEY. We should return the address of the node deleted in a pointer named P, or we should return the null pointer if the key is not found.
L = A(LSTHEADER)
P = L->LHLINK
IF (P = NULL) List is empty, return null
RETURN NULL
ELSE
IF (P->KEY = DLTKEY) If node to delete is first in list
L->LHLINK = P->LINK adjust listheader link
RETURN (P)
ELSE
SET FLAG ON
DO WHILE (P NE NULL AND FLAG ON) Search the list for the node
IF (P->KEY >= DLTKEY)
SET FLAG OFF
ELSE
L = P
P = P->LINK
ENDIF
ENDDO Here, P -> node with delete key, or P-> node with key greater than delete key, or P is null
IF (P = NULL)
RETURN NULL
ELSE
IF (P->KEY = DLTKEY)
L->LINK = P->LINK Adjust pointer of node behind node P
RETURN (P)
ELSE
RETURN NULL
ENDIF
ENDIF
ENDIF
ENDIF
An algorithm to insert a node into a circular doubly linked list with a list header. Assume pointer Q has address of new node to insert
L = A(LSTHEADER) pointer L will always address the listheader
P = L-->LHFLNK P --> 1st node in list or is null if list is empty
IF (P = NULL) insert new node as first & only node in list
L-->LHFLNK = Q point listheader's forward and back link fields to node Q
L-->LHBLNK = Q
Q-->FLNK = L point node Q's forward and back link fields to listheader
Q-->BLNK = L
ELSE
IF (P-->KEY GE Q-->KEY) new node is 1st in existing list
L-->LHFLNK = Q
P-->BLNK = Q
Q-->FLNK = P
Q-->BLNK = L
ELSE search list for location to insert
SET FLAG ON
DO WHILE (P NE L .AND. FLAG ON)
IF (P-->KEY GE Q-->KEY)
SET FLAG OFF
ELSE
P = P-->FLNK
ENDIF
ENDDO
/* at this point P points to node following correct location to insert node Q. P may be addressing the Listheader. If so, the new node goes in the list as the new "last" node. */
IF (P NE L) not back to listheader
R = P-->BLNK
ELSE
R = L-->LHBLNK
ENDIF
/* pointer R addresses the node in front of which node Q is to be inserted
Q-->BLNK = R
Q-->FLNK = P
R-->FLNK = Q
IF (P NE L)
P-->BLNK = Q
ELSE
L-->LHBLNK = Q
ENDIF
ENDIF
ENDIF
An algorithm to delete a node from a circular doubly linked list with a header. Assume variable named DLTKEY has key of node to delete
L = A(LSTHEADER) pointer L will always address the listheader
P = L-->LHFLNK P --> 1st node in list or is null if list is empty
IF (P = NULL)
RETURN NULL
ELSE
Q = P-->FLNK Q points to node following P (or maybe -->ListHdr)
IF (P-->KEY = DLTKEY) delete node is 1st in list
IF (Q = L) delete node is 1st and only
NULL OUT LISTHDR BLNK AND FLNK
ELSE
/* node to delete is 1st in list, but list has more than one node
Q-->BLNK = L
L-->LHFLNK = Q
ENDIF
RETURN P
ELSE search list for node to delete
SET FLAG ON
DO WHILE (P NE L .AND. FLAG ON)
IF (P-->KEY GE DLTKEY)
SET FLAG OFF
ELSE
P = P-->FLNK
ENDDO
/* see if we're back to listheader. If so, node not found
IF (P EQ L) back to listheader
RETURN NULL
ELSE
/* see if we found the delete node
IF (P-->KEY = DLTKEY)
F = P-->FLNK F--> node in front of delete-node
R = P-->BLNK R--> node in back of delete-node
R-->FLNK = F
/* check to see if node we're deleting is "last" in list.
IF (F = L)
L-->LHBLNK = R
ELSE
/* if node to delete is not last in list, adjust front node's BLNK pointer
F-->BLNK = R
ENDIF
RETURN P
ELSE
RETURN NULL
ENDIF
ENDIF
ENDIF
ENDIF