Operations on Linked Lists

 

We studied the fundamentals of linked lists in previous lesson. Linked lists are dynamic data structures where nodes can be added, deleted or updated with a minimal cost. Also linked lists do not require access to a large contiguous block of memory at compile time, but rather accessing memory as needed during runtime. This flexibility makes linked lists attractive data structures for many practical applications.

 

In this lesson, we will focus on some of the basic operations on linked lists such as adding, deleting and updating node elements. In an array, adding or deleting an entry requires shifting of the array to “fill” or “create” holes. Updating an entry in an array only requires accessing entry by its index and changing its value. One of the best features of the array data structure is its ability to access entries in a random access manner. That is, given the index of the entry we can easily find it.

Unlike arrays, the entry point into any linked list is the head of the list. Head of the list is not a node but a reference to the first node in the list. In other words, head can be considered a lvalue. In an empty list the value of head is equal to null. We also know that any linked list ends with null pointer (unless it is a circular linked list where last node is connected to the head node). We must take great care in manipulating linked lists since any misguided link in the middle will make the entire list inaccessible. This is because the only way to navigate a list is by using a reference to the next node from the current node. Often referred as “memory leaks”, if a reference to a node is lost, then the entire list from that point on may not be accessible.

 

BASIC OPERATIONS

Some of the basic operations that can be performed on a linked list are

1.      Traversing a linked list.

2.      Appending a new node (to the end) of the list

3.      Prepending a new node (to the beginning) of the list

4.      Inserting a new node to a specific position on the list

5.      Deleting a node from the list

6.    Updating the data of a linked list node

 

Traversing a Linked List

A linked list is a linear data structure that needs to be traversed starting from the head node until the end of the list. Unlike arrays, where random access is possible, linked list requires access to its nodes through sequential traversal. Traversing a linked list is important in many applications. For example, we may want to print a list or search for a specific node in the list. Or we may want to perform an advanced operation on the list as we traverse the list. The algorithm for traversing a list is fairly trivial.

a.       Start with the head of the list. Access the content of the head node if it is not null.

b.      Then go to the next node(if exists) and access the node information

c.       Continue until no more nodes (that is, you have reached the last node)

 

Appending a new Node to the end of the list

Sometimes we need to append (or insert to end) new nodes to the end of a list. Since we only have information about the head of the list, we need to traverse the list until we find the last node. Then we insert new node to the end of the list. In this case, it is important to consider special cases such as list being empty.

 

 

               

                 head                                      last

 

 

Let us consider a method append that inserts nodes to the end of the list.

public void append(Node N ) {

   Node ptr, prev;

    ptr = prev = head;

    while (ptr != null)   ptr = ptr.next;  // assume next is a public field in the node class

    prev.next = N;  N.next = null;

}

Question: Does this code always work? Can you find a case where the code fails to work?

 

Prepending a new Node to the beginning of the list

Let us try to prepend a new node to the beginning of a list or in other words insert a node to the beginning of the list. Prepending a node to a list is easy since there is no need to traverse the list and find the place to insert into the list. If list is empty, we make new node the head of the list. Otherwise, we connect new node to the current head of the list and make new node the head of the list.

 

 

            

                  New head             Old  head    

 

 

public void prepend(Node N ) {

    if (head == null)  head = N;

    else { N.next = head; head = N;} 

}

Question: Does this code always work? Can you find a case where the code fails to work (if any)?

 

 

 

 

 

 

 

Inserting a new Node to an arbitrary position in the list

Suppose we need to insert (to some specific location) a new node to a list. It is important that we traverse the list to find the place to insert the node. In the traversal process, we must maintain a reference to previous and next nodes of the list. Then we will insert a new node between previous and next.

 

new

 
 
 

                

                  prev                                       ptr

 

 

 

public void insertInOrder(Node N ){

      Node prev, ptr;

      prev = ptr = head;

      while (ptr != null && N.compareTo(ptr) > 0) { prev = ptr; ptr = ptr.next;}

      prev.next = N;  N.next = ptr;

 }

 

Question: Are all cases covered in the above code?

We did use few methods like compareTo in the above code. Our assumption is that compareTo method is implemented by our Linked List class. We also assume that our linked list class has implemented the Comparable interface. compareTo method returns 0, 1 or -1 based on if the first node is equal, bigger or less than the second node.

 

Deleting a Node from the list

To delete a specific node from the list (if the node exists). It is important that we traverse the list to find the node to delete. In the traversal process, we must maintain a reference to previous node of the list. Unlike in other programming languages (such as C) we don’t need to worry about deallocating memory associated with the deleted node, since Java garbage collector takes care of this.

 

delete

 
 
 

                     

                     prev                             

 

 

Let us take a look at the code to delete a node.

public void delete(Node N ) {

     Node prev, ptr;

     while (ptr != null &&  ptr.compareTo(N) != 0)  { prev = ptr; ptr = ptr.next;}

     if (ptr == null)  return;

     prev.next = ptr.next;

}

Question: Does the above code covers all special cases of deleting a node? What if the node does not exists? What if the node to be deleted turns out to be the very first node? What if node to be deleted turns out to be the last node in the list?  

 

Conclusion

In this lesson we learned how to traverse, append, prepend, insert and delete nodes from a linked list. These operations are quite useful in many practical applications. Suppose you are the programmer responsible for an application like Microsoft powerpoint. We can think of a powerpoint presentation as a list, whose nodes are the individual slides. In the process of creating and managing slides we can use the concepts such as inserting and deleting nodes learned in this lesson. Many other applications may require you to think of an abstraction like a list, where list can be easily maintained. In the next lesson we will learn more advanced list operations such as reversing a list, swapping nodes and sorting a list etc. Linked lists remain one of the widely used concepts in programming applications. More advanced linked list structures like an array of linked lists, or linked list of linked lists or multilinked lists can be used to implement applications that require complex data structures.