Operation 8 – List Count/Size:

List count is another simple, one-line module. It is necessary because the calling module has no direct access to the list structure. Its implementation is shown in Algorithm 8.

Algorithm – 8 Linked list count

algorithm listCount (val list )

Returns integer representing number of nodes in list.

Pre list is metadata structure to a valid list

Return count for number of nodes in list

1 return (list. count)

end listCount

Operation 6 IS – Empty List, Operation 7 IS – Full List :

Processing logic often depends on whether there are data in a list. Thus, we provide empty list, a simple module that returns a Boolean indicating that there are data in the list or that it is empty (Algorithm 6).

Empty linked list

algorithm emptyList (val list )

Returns Boolean indicating whether the list is empty.

Pre list is metadata structure to a valid list

Return true if list empty, false if list contains data

1 return (list.count equal to zero)

end emptyList

Full List :

At first glance, full list appears to be as simple as empty list. It turns out to be a relatively complex algorithm to implement, however. Very few languages provide the programmer with the capability to test how much memory is left in dynamic memory. Given this limitation, the only way we can test for a full list is to try to allocate memory. If we are successful, we simply recycle the memory and return false – the list is not full. If we are unsuccessful, then we return true – dynamic memory is full. The pseudocode is shown in Algorithm 7.

Algorithm – 7 Full linked list

algorithm fullList (val list )

Returns Boolean indicating whether or not the list is full.

Pre list is metadata structure to a valid list

Return false if room for new node; true if memory full

1 allocate (pNew)

2 if (allocation successful)

1 recycle (pNew)

2 return false

3 end if

4 return true

end fullList

Operation 5 – Retrieve Node :

After knowing how to locate a node in the list, we can retrieve data from that node. Retrieve node uses search mode to locate the data in the list. If the data are found, it moves the data to the output area in the calling module and returns true. If they are not found, it returns false. The pseudocode is shown in Algorithm 5.

Algorithm – 5: Retrieve linked list node

algorithm retrieveNode (val list ,

val key ,

ref dataOut )

Retrieves data from a linked list.

Pre list is metadata structure to a valid list

key is target data to be retrieved

dataOut is variable to receive retrieved data

Post data placed in dataOut

-or- error returned if not found

Return true if successful, false if data not found

1 found = searchList (list, pLoc, key)

2 if (found)

1 dataOut = pLoc->data

3 end if

4 return found

end retrieveNode

Operation 4 – Search List :

A Search list is used by several algorithms to locate data in a list. To retrieve data from a list, we need to search the list and find the data. In addition, many user applications require that lists be searched to locate data. We present an algorithm to search for a key in an unordered list.

For simplicity, we assume that all data values in the list are unique that no data value is repeated.

Algorithm – 4: Search Unordered Linked List

algorithm searchunorderedlist (val list ,

ref pLoc ,

val key )

Searches list and passes back address of node containing key.

Pre list is metadata structure to a valid list

pLoc is pointer to variable for current node

key is the target being sought

Post pLoc points to node with equal data

-or- null if key is not found

Return true if found, false if not found

1 pLoc = list.head

2 loop (pLoc not null AND key not equal pLoc->data)

1 pLoc = pLoc->link

3 end loop

Set return value

4 if (pLoc null)

1 found = false

5 else

1 if (key equal pLoc->data)

1 found = true

2 end if

6 end if

7 return found

end searchList

Operation 3 – Delete Node :

The delete node algorithm logically removes a node from the linked list by changing various link pointers and then physically deleting the node from dynamic memory. To logically delete a node, we must first locate the node itself. A delete node is located by knowing its address and its predecessor’s address. Once we locate the node to be deleted, we can simply change its predecessor’s link field to point to the deleted node’s successor. We then recycle the node back to dynamic memory. We need to be concerned, however, about deleting the only node in a list. Deleting the only node results in an empty list, so we must be careful that in this case the head is set to a null pointer.

The delete situations parallel those for add. We can delete the only node, the first node, a node in the middle of the list, or the last node of a list. As we explain below, these four situations reduce to only two combinations: delete the first node and delete any other node. In all cases, the node to be deleted is identified by a pointer (pLoc).


Operation 3a – Delete First Node or Only Node :
When we delete the first node, we must reset the head pointer to point to the first node’s successor and then recycle the memory for the deleted node. We can tell we are deleting the first node by testing the predecessor. If the predecessor is a null pointer, we are deleting the first node. This situation is diagrammed in Figure 15.

The statements to delete the first node are shown below. Recycle is the pseudocode command to return a node’s space to dynamic memory.

If you examine this logic carefully, you will note that it also applies when we are deleting the only node in the list. If the first node is the only node, then its link field is a null pointer. Because we move its link field (a null pointer) to the head pointer, the result is by definition an empty list.

Operation 3b – Delete Middle or Last Node Case :

Same logic applies to deleting any node in either the middle or at the end of the list. For both of these cases, we simply point the predecessor node to the successor of the node being deleted. The logic is shown in Figure 16.

We delete the last node automatically. When the node being deleted is the last node of the list, its null pointer is moved to the predecessor’s link field, making the predecessor the new logical end of the list. After the pointers have been adjusted, the current node is recycled.

The delete general case pseudocode is shown below in the inset of figure 16.

Operation 3c – Delete Node Algorithm :

The logic to delete a node is shown in Algorithm 3. The algorithm is given a pointer to the head of the list, to the node to be deleted, and to the delete node’s predecessor. It copies the deleted node’s data to a data out area in the

calling program and then adjusts the pointers before releasing the node’s memory.

Algorithm – 3 Linked list delete node

algorithm deleteNode (ref list ,

val pPre ,

val pLoc ,

ref dataOut )

Deletes data from a linked list and returns it to calling module.

Pre list is metadata structure to a valid list

pPre is a pointer to predecessor node

pLoc is a pointer to node to be deleted

dataOut is variable to receive deleted data

Post data have been deleted and returned to caller

1 dataOut = pLoc->data

2 if (pPre null)

Deleting first node

1 list. head = pLoc->link

3 else

Deleting other nodes

1 pPre->link = pLoc->link

4 end if

5 list.count = list.count – 1

6 recycle (pLoc)

7 return

end deleteNode

Operation 2  Insert Node :

Insert Node adds data to a linked list. We need only its logical predecessor to insert a node into the list. Given the predecessor, there are three steps to the insertion :

1. Allocate memory for the new node and insert data.

2. Point the new node to its successor.

3. Point the new node’s predecessor to the new node.

These steps appear to be simple, but a little analysis is needed to fully understand how to implement them. To insert a node into a list we need to know the location of the node that precedes the new node. This node is identified by a pointer that can be in one of two states : it can contain the address of a node or it can be null. When the predecessor is null, it means that there is no predecessor to the data being added. The logical conclusion is that we are either adding to an empty list or are at the beginning of the list. If the predecessor is no null, then we are adding somewhere after the first node – that is, in the middle of the list or at the end of the list. Let’s discuss each of these situations in turn.

Operation 2a ¾ Insert into Empty List :

When the head pointer of the list is null, then the list is empty. This situation is shown in Figure 11. All that is necessary to add a node to an empty list is to assign the list head pointer the address of the new node and make sure that its link field is a null pointer. Although we could use a constant to set the link field of the new node, we use the null pointer contained in the list head. Why we use the list head null pointer will become apparent in the next section.

Node the order of these two statements. We must first point the new node to its successor; then we can change the head pointer. If we reverse these statements, we will end up with the new node pointing to itself, which would put our program into a never-ending loop when we process the list.

Operation 2b ¾ Insert at Beginning :

We add at the beginning of the list anytime we need to insert a node before the first node of the list. We determine that we are adding at the beginning of the list by testing the predecessor pointer. If it is a null pointer, then there is no predecessor so we are at the beginning of the list.

To insert a node at the beginning of the list we simply point the new node to the first node of the list and then set the head pointer to point to the new first node. We know the address of the new node. The question at this point is how we can find the address of the first node currently in the list so we can point the new node to it. The answer is simple. The first node’s address is stored in the head pointer. The pseudocode statements to insert at the beginning of the list are shown in the inset of figure 12.

If you compare these two statements with the statements to insert into an empty list, you will see that they are the same. They are the same because, logically, inserting into an empty list is the same as inserting at the beginning of a list.

Operation 2c ¾ Insert in Middle :

When we add a node anywhere in the middle of the list, the predecessor contains an address. This case is shown in Figure 13.

To insert a node between two nodes, we point the new node to its successor and then point its predecessor to the new node. The address of the new node’s successor can be found in the predecessor’s link field.

Operation 2d ¾ Insert at End :

When we are adding at the end of the list, we only need to point the predecessor to the new node. There is no successor to point to. It is necessary, however, to set the new node’s link field to a null pointer. The statements to insert a node at the end of a list are shown below in the inset of figure 14.

We can take advantage of the existing linked list structure. We know that the last node in the list will have a null link pointer. If we use this pointer rather than a null pointer constant, then the code becomes exactly the same as the code for inserting in the middle of the list.

General Insert Node Algorithm :

Now let’s write the algorithm that puts it all together and inserts a node into the list. We are given the head pointer, the predecessor, and the data to be inserted. We allocate memory for the new node and adjust the link pointers appropriately. When the algorithm is complete, it returns a Boolean – true if it was successful and false if there was no memory for the insert. The pseudocode is found in Algorithm 2.

Algorithm – 2 Insert linked list node

algorithm insertNode (ref list ,

val pPre ,

val dataIn )

Inserts data into a new node in the linked list.

Pre list is metadata structure to a valid list

pPre is pointer to data’s logical predecessor

dataIn contains data to be inserted

Post data have been inserted in sequence

Return true if successful, false if memory overflow

1 allocate (pNew)

2 if (memory overflow)

1 return false

3 end if

4 pNew->data = dataIn

5 if (pPre null)

Adding before first node or to empty list.

1 pNew->link = list. head

2 list. head = pNew

6 else

Adding in middle or at end.

1 pNew->link = pPre->link

2 pPre->link = pNew

7 end if

8 list.count = list.count + 1

9 return true

10 end insertNode

Linked List Operations, Operation 1: Create a Linked List

Earlier, we have defined the head structure “list” and the node structure “node”. Fields of both structures are not initialized yet i.e, the member variables are not assigned values. Only structures exists, as shown in figure a & b.

The following algorithm will initialize the list to an empty state. Later on nodes can be added or deleted as the need arises. After the execution of the algorithm, the situation is shown in figure b.

Create List receives the head structure and initializes the metadata for the list. At this time, there are only two metadata entries; later we can add more to expand the capabilities of the linked list. Figure shows the header before and after it is initialized by create list.

Algorithm – 1 Create linked list

algorithm creatList (ref list )

Initializes metadata for a linked list.

Pre list is metadata structure passed by reference

Post Metadata initialized, and list is empty

1 list list1;

2 list1.head = null;

3 list1.count = 0;

4 return;

end creatList