Linked List Algorithms

Implementation:

~ Several data structures can be used to implement a list; we use a linked list.

~ A linked list is a good structure for a list because data are easily inserted and deleted at the beginning, in the middle, or at the end of the list. 

Data Structure:

~ To implement a list, we need two different structures, a head node and data node.

Algorithms:

~ We define 10 operations for a list, which should be sufficient to solve any problem.

~ If an application requires additional list operations, they can be easily added.

~ For each operation we define its name and provide a brief description and its calling parameters.

~ We then develop algorithms for each operation.

Create List:

~ Create list allocates the head structure and initializes the metadata for the list.

Insert Node:

Insert node adds data to a list. 

1. Allocate memory for the new node and move data to the node.

2. Point the new node to its successor.

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

~ 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 predecessor 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 pointer 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 not null, we are adding somewhere after the first node—that is, in the middle of the list or at the end of the list.

Insert into Empty List:

~ When the head pointer of the list is null, the list is empty.

~ To add a new node, the list head pointer should be assigned the address of the allocated or new node and make sure that its link field is a null pointer.

Insert at Beginning:

Insert in Middle:

Insert at End:

Insert Node Algorithm:

Delete Node:

~ The delete node algorithm logically removes a node from the list by changing

various link pointers and then physically deleting the node from dynamic

memory.

~ Locate the node to be deleted by knowing its address and its predecessor’s address.

~ Change the predecessor’s link field to point to the

deleted node’s successor.

~ We then recycle the node back to dynamic memory.

~ If deleting the only node in a list. results in an empty list, and set the head to a null pointer.

Delete First Node:

General Delete Case:

Delete Node Algorithm:

Search List/List Search:

~ A list search is used by several algorithms to locate data in a list.

~ To insert data, we need to know the logical predecessor to the new data.

~ To retrieve data from a list, we need to search the list and find the data.

Ordered List Search:

~ When the data are stored in a linked list, however, we can't use a binary search.

~ We must use a sequential search because there is no physical relationship among the nodes.

~ The classic sequential search1 returns the location of an element when it is found and the address of the last element when it is not found.

~ To return the location of the element when it is found and the location where it should be placed when it is not found. Knuth2 calls this search “sequential search in ordered table.” or Ordered List Search.

Note: If a node in the list matches the target value, the search returns true; if there are no key matches, it returns false.

Analysis:

.

• The first test protects us from running off the end of the list; the second test stops the loop when we find the target or, if the target doesn’t exist, when we find a node larger than the target.

• It is important that the null pointer test be done first. If the loop is at the end of the list, the current pointer is no longer valid.

• Testing the key first would give unpredictable results.

Unordered List Search:

o To search a list on any field other than the key, we use a simple sequential search.

o The problem with non-key searches, however, is that multiple elements often satisfy the search criteria. 

o Although we might have only one employee who speaks Japanese, we might just as well have zero or many who do.

o One simple solution is to return a list of all elements that satisfy the criteria.

Retrieve Node:

1. Now that we know how to locate a node in the list, we are ready to study retrieve node.
2. Retrieve node uses search node to locate the data in the list. 
3. If the data are found, it moves the data to the output area in the calling module and returns true.
4. If they are not found, it returns false.

Empty List:

~ Processing logic often depends on there being data in a list.

~ We provide empty list, a simple module that returns a Boolean indicating that there are data in

the list or that it is empty.

Full List:

~ At first glance, full list appears to be as simple as empty list. 

~ As we saw with stacks, however, it turns out to be a relatively complex algorithm to implement.

~ Very few languages provide the programmer with the capability to test how much memory is left in dynamic memory—C does not.

List Count:

List count is another simple, one-line module. It is necessary because the calling module has no direct access to the list structure.

Traverse List:

~ Algorithms that traverse a list start at the first node and examine each node in succession until the last node has been processed. 

~Traversal logic is used by several different types of algorithms, such as changing a value in each node,

printing the list, summing a field in the list, or calculating the average of a field.

~ Any application that requires that the entire list be processed uses a traversal.

~To traverse the list, we need a walking pointer, a pointer that moves from node to node as each element is processed.

~ We have two possible approaches in designing the traverse list implementation. 

~ In one approach the user controls the loop, calling traverse to get the next element in the list.

~ In the other approach, the traverse module controls the loop, calling a user-supplied algorithm to process the data.

~ We implement the first option because it provides the programmer with more flexibility.

~ We need to remember where we are in the list from one call to the next, we need to add a current position pointer to the head structure.

~ It keeps track of the node processed after the last call.

~ The position pointer is modified to move from one node to the next as the traversal algorithm is called.

~ Each call also needs to know whether we are starting from the beginning of the list or continuing from the last node processed.

Destroy List:

~ When a list is no longer needed but the application is not done, the list should be destroyed.

~ Destroy list deletes any nodes still in the list and recycles their memory.