Linked Lists – Advanced Operations

In the previous lessons we learned some basic operations that can be performed on linked lists. In particular, we discussed how to append, prepend, insert and delete nodes to/from a linked list. In this lesson we learn some advanced operations that can be performed on linked list. We will also discuss how to generalize the singly linked list methods to a more complex data structure like a doubly linked list or a multilinked list. We will start with some advanced operations on singly linked lists.

Reversing a List
One of the useful operations that can be performed on linked lists is to reverse a linked list. A naive algorithm for doing this is to remove the first node of the list, insert to the beginning of a new list, then remove the second node (which now has become first node) and insert to the beginning of the new list etc. If the list has n nodes, then after performing n of these operations, we would have reversed the list. The following diagrams illustrate this process.

Original List

1

2

3

Delete first node and insert to the beginning of a new list.

1

Delete the second node and insert to the beginning of the new list etc..

3

This algorithm requires one to carefully manage removing nodes from the old list and adding nodes to the new list. Even if the new nodes are not created, complex pointer manipulations is necessary.

Exercise: Complete the method

public myList reverese(myList L); that reverses the list L and returns a reference to the new list.

An Alternate Algorithm

So can we find a better algorithm for reversing the list? One possibility is to reverse the links without deleting or inserting nodes. The following figure illustrates the process.

Last node

head

In this algorithm, the next reference can be reversed as we traverse the list.

Exercise: Complete the method

public myList reverese(myList L);

that reverses the list L and returns a reference to the new list using new algorithm that reverses the links.

Cloning Linked Lists

Let us begin by evaluating the following code

LinkedList list = new LinkedList();

list.prepend(new Node("first"));

list.append(new Node("last"));

LinkedList list2 = list;

The reference list2 is an alias, it points to the same object as list1. This means that once we change list, these changes occur in list2 as well. In this case, we consider list2 as a shallow copy of list1. In other words, list1 and list2 shares the same nodes in one linked list. In many cases it will be quite useful to have a deep copy of an object. To create a deep copy, we need to duplicate all nodes in the list. For this purpose, the Object class provides the method clone(), which we will override in the LinkedList class:

public Object clone() throws java.lang.CloneNotSupportedException

{

LinkedList twin = new LinkedList();

if(head == null) return twin;

Node tmp = head;

for(int i = 0; i < size; i++)

{

twin.append(tmp.data);

tmp = tmp.getNext();

}

return twin;

}

As you know append() is quite expensive operation, because each time you need to traverse the whole list to append a node.

Exercise: rewrite the clone method assuming there is a prepend method in your LinkedList class.

Sorting a Linked Lists

Sorting a List is one of the common operations that are performed. Sorting an array of object can easily be done using sorting algorithms like bubble, insertion or quick sort. However, sorting a linked list is not that trivial since linked list nodes cannot be randomly accessed. Only useful way to sort a linked list is to remove a node from the old list and insert into a new list in order. However for large lists, this is not very practical as insertion sort requires O(n²) operations. An alternative method is to define a toArray method for the linked list class that allows the linked list to be converted to an array first and then apply a more efficient algorithm like quick sort to sort. Once sorted the array can be converted into a linked list again. This is still more efficient in theory as toArray, sorting using qsort, constructing a linked list from an array takes O(n), O(n log n) and O(n) operations respectively. Asymptotically this is still better than O(n²) performance of a slow sort.

Doubly Linked Lists

We briefly discussed the concept of doubly linked list in lesson 1. Each node in a doubly linked list has a reference to the previous node. A good exercise is to write append, insert and remove methods for a doubly linked list. In a singly linked list, insert requires changing two references. Generalizing this to a doubly linked list requires changing four references (two for next and two for prev). We need to take great care in the order we perform these four operations, as incorrect order may create lists with nodes that have self references, creating an infinite loop during the traversal of the list.

An Array of Linked Lists

Another useful data structure to consider is an array of linked lists. This type of a structure allows us to use two indices, the array index and linked list position to locate a particular node. For example, you can maintain a priority queue as an array of linked lists, where next element to process is selected from the array index based on the priority. Here is a picture of a priority queue implementation using

In this implementation we assume that array index indicates the priority of the list and each list is a queue where next element to process is the first node of the list. In this case removing a node from a list is easy (as nodes are removed from the front) but adding a node to a list is expensive, requiring us to traverse the list to find the end of the list.