Other Linked List Variations

We introduce two other useful linked list variations – the circularly linked list and the doubly linked list.

Circularly linked list

In the circularly linked list, the last node’s link points to the first node of the list, as shown in Figure 18. Circularly linked list are primarily used in structures that allow access to nodes in the middle of the list without starting at the beginning. In circular list, nodes form a ring: The list is finite and each node has a successor.

Insertion and deletion into a circularly linked list follow the same logic used in singly linked list except that the last node points to the first node. Therefore, when inserting and deleting the last node, in addition to updating the rear pointer in the header, we must also point the head field to the first node.

Given that we can directly access a node in the middle of the list through its data structure, we are then faced with a problem when searching the list. If the search target lies before the current node, how do we find it? In a singly linked list, when we arrive at the end of the list the search is complete. In a circular list, however we automatically continue the search from the beginning of list.

The ability to continue the search presents another problem. What if the target does not exist? In the singly linked list, if we did not find the data we are looking for, we stopped when we hit the end of list. With a circular list, we save the starting node’s address and stop when we have circled around to it, as shown code below.

Loop (key not equal to pLoc->node.data

AND pLoc->link not equal to startAddress)

Circular list, in which the last node is followed by the first node, is usually preferable to non-circular one, for two reasons:

• They provide easy access to both ends of a list: notice that we do not need the first pointer in the header, because we can easily reach the first node with rear -> link -> data
• the code for processing a circular list is often simpler than the code for processing a non-circular list - mainly because you don't have to constantly check if the next node is defined - it is always defined.

At the implementation level, however, circularity does create one very tricky case that is a very common source of bugs, and that is singleton lists. When there is only one node in a circular list, it points to itself as the next node.

Doubly Linked or Two-way Linked Lists

One of the most powerful variations of linked lists is the doubly linked list. A doubly linked list is a linked list structure in which each node has a pointer to both its successor and its predecessor. Figure 19 is a representation of a doubly linked list.

There are three pieces of metadata in the head structure: a count, a head pointer, and a rear pointer. Although a rear pointer is not required in all doubly linked lists, it makes some of the list algorithms, such as insert and search, more efficient.

Each node contains two pointers, a backward pointer to its predecessor and a forward pointer to its successor. In Figure 19 these pointers are designated B and F, respectively.

Another variation on the doubly linked list is the doubly linked circularly linked list. In this variation, the last forward pointer points to the first node of the list and the backward pointer of the first node points to the last node. If there is only one node in the list, both the forward and backward pointers point to the node itself.

Doubly Linked List Insertion

Inserting a node into a doubly linked list follows the basic pattern of inserting a node into a singly linked list, but we also need to connect both the forward and backward pointers.

A null doubly linked list’s head and rear pointers are null. To insert a node into a null list, we simply set the head and rear pointers to point to the new node and set the forward and backward pointers of the new node to null. The results of inserting a node into a null list are shown in Figure 20(a).

Figure 20(b) shows the case for inserting between two nodes. The new node needs to be set to point to both its predecessor and its successor, and they need to be set to point to the new node. Because the insert is in the middle of the list, the head structure is unchanged except for adding to the count.

Inserting at the end of the list requires that the new node’s back pointer be set to point to its predecessor. Because there is no successor, the forward pointer is set to null. The rear pointer in the head structure must also be set to point to the new rear node.

Algorithm 22 contains the code to insert a node into a doubly linked list.

Algorithm – 12 Doubly linked list insert

algorithm insertDbl (ref list ,

pPre ,

pSucc ,

val dataIn )

This algorithm inserts data into a doubly linked list.

Pre list is metadata structure to a valid list

PPre is pointer variable for predecessor

PSucc is pointer variable for successor

dataIn contains the data to be inserted

Post The data have been inserted in sequence

Return 0 : failed—dynamic memory overflow

1 : successful

1 if (full list)

1 return 0

2 end if

3 allocate (pNew)

4 pNew->data = dataIn

Locate insertion point in list

5 if (pPre is null)

Inserting before first node or into empty list

1 pNew->back = null

2 pNew->fore = list.head

3 list.head = pNew

6 else

Inserting into middle or end of list

1 pNew->back = pPre

2 pNew->fore = pPre->fore

3 pPre->fore = pNew

7 end if

Test for insert at end of list and also check not empty list

8 if (pPre->fore null and pPre not null)

Inserting at end of list –set rear pointer

1 list.rear = pNew

9 else

Inserting in middle of list — point successor to new

1 if (pSucc not null) check not empty list

1 pSucc->back = pNew

10 end if

11 list.count = list.count + 1

12 return(1)

end insertDbl