# Linked Lists and Iterative Algorithms

## CS 112

These notes are an introduction to the notion of linked lists of nodes in Java. The topics we cover are as follows:

1. Basic notions of linked lists;
3. A "cookbook" of the most useful iterative algorithms; and
4. Using "dummy" header nodes to reduce the number of special cases.

The algorithms are generally presented as Java functions (methods) operating on lists of integers, however, note that the data contained in the nodes could be a generic type.

## Basic Principles of Linked Lists

### Basic data declarations

All the code below assumes the following declaration:

```   public class Node {

public int item;
public Node next;

Node() {                 // this would be the default, put here for reference
item = 0;
next = null;
}

Node(int n) {
item = n;
next = null;
}

Node(int n, Node p) {
item = n;
next = p;
}
};

Node head = null;      // pointer to the head of a list

```
```
```

These constructors will simplify a number of the algorithms below. For example, to create a list with one element containing the item 5, we could write:

```     head = new Node();
head.next = null;          // not actually necessary, since pointers are initialized to null by default```

or we can simply use the constructor:

```     head = new Node(5);
```

Either will produce:

To add a node containing a 5 to the front of an existing list

we could write

```   head = new Node();

or use the constructor:

```   head = new Node(5, list);
```

either of which produces the follow data structure:

We can also "splice" a node into the middle of an existing list, as long as we have a pointer to the node right before the splice; suppose we have a list and a pointer `p` to a node in the list:

We can add a new node containing 5 after `p` (i.e., between the node `p` and the node `p.next`) by writing:

```   Node q = new Node();
q.item = 5;
q.next = p.next;
p.next = q;```

which produces:

Or we can use the constructor:

```   p.next = new Node(5, p.next);
```

which produces the same list but without the temporary variable `q`:

Note that it can also be used to create simple linked lists in a single Java statement. For example, the list just created by splicing could alternately have been created by the following single statement.

```   Node list = new Node(6, new Node(2, new Node(5, new Node(1))));

```

In many cases, you have one or more linked lists stored in an ADT object, and you need to manipulate them using ADT methods, and everything is private inside the object. This is the case, for example, in the stack and queue ADT examples of linked lists we studied in lecture. The head pointer, and all the method are private members of the class, for example, here is an object D with an internal linked list and associated methods:

We will assume for the present that we are manipulating a single linked list in this fashion.

#### Adding to front of a list

The declarations above create an empty list:

``` Node head = null;
```

To add to the front of the list, just use the constructor as shown above, changing the pointer head to put a new node between it and the node it points to:

```  void addToFront(int n) {
}

```

So, here is the result of three calls to addToFront, starting from an empty list:

` addToFront(1, head); `

` addToFront(2, head); `

` addToFront(6, head); `

#### Removing the first node in a list

Do the reverse of the previous method is also a simple example of list manipulation; here we will remove the first element and return the number in the node removed

```  int removeFront() {
int temp = head.item;               // does no error checking for empty lists!
return temp;
}
```

You should have recognized the previous two methods as identical to push and pop on a stack!!

#### Basic chaining to access each element of a list

The basic thing you do with a list is to "chain along" the list, setting a pointer `p` to each node in turn and performing some operation at each node (such as printing out the list). This is done with a simple `for` loop that initializes a reference to the first node and stops when it reaches null. At each iteration of the loop, p will point to each node in the list in turn:

```    for(Node p = head; p != null; p = p.next ) {

// Do something with each node, such as print out the item

}

OR use a while loop:

while (p != null) {
// Do something with each node, such as print out the item
p = p.next;
}
```

This produces the following at each successive iteration of the loop:

At the last iteration, p chains along one more time to point to null, and the `for` loop ends:

Note we are guaranteed by the loop condition that `p` is not `null` inside the loop, so we can refer to `p.item` or `p.next` anytime we want inside the loop without worrying about `NullPointerExceptions`.

#### Printing Out A List

We can then put this code inside a method to do something specific to each member of the list, such as printing it out. Remember that these methods exist inside an object with a global field `head` pointing to a linked list.

```  void printList() {
for(Node p = head; p!=null; p = p.next) {
System.out.print(p.item + " -> ");
}
System.out.println(".");
}  ```

#### Producing a String representation of the list

If we want to produce a String representation for the `toString()` method the ADT, we can do the same thing but collect the results and return them:

```  public String toString() {
String s = "head -> ";
for(Node p = head; p!=null; p = p.next) {
s += (p.item + " -> ");
}
return s + ".";
}```

#### Finding the Length of a List

Another simple example would be finding the length of a list, which can be done by simply keeping a running count inside the for loop:

```    int length() {
int count = 0;
for(Node p = head; p != null; p = p.next ) {
++count;
}
return count;
}
```

Exercise A (you may assume the input lists are non-empty):

1. Write a method which returns the sum of the numbers in the list.
2. Same, but returns the average of the numbers in the list;
3. Same, but returns the last number in the list.

#### Chaining down the list and stopping at the end or upon some condition

Suppose we wish to find the first node in the list satisfying some Boolean condition B (e.g., we are looking for a particular item k, so B would be `p.item == k`). A simple modification of the previous technique is to add an `if` statement to the loop, possibly jumping out of the loop after executing some statements:
```        for(Node p = head; p != null; p = p.next )
if( B ) {
// do something to the node that p refers to
break;   // if you want to stop the chaining along
}```

Note, again, that we can refer to `p.item` and `p.next` in the loop body with no worry of a `NullPointerException`, because we have already checked that `p != null` in the for loop condition. A more compact way of writing this loop is to put the negation of the if-statement condition into the `for` loop condition:

```        for(Node p = head; p != null && !B; p = p.next ) {
// etc.
}```
For example, if we wish to set the pointer q to point to the first negative number in the list (or null if no such number exists) we could write the following:
```        Node q = null;
for(Node p = head; p != null && p.item >= 0; p = p.next ) {
q = p;
}

// now q points to first negative number or null if not found
```
Note that we have to move the delaration of the loop variabe outside the loop if we wish to refer to it after the loop; so we could the same as the previous more compactly as follows:
```        Node q = null;
for(   ; q != null && q.item >= 0; q = q.next ) {
;
}

// now q points to first negative number or null if not found

OR, use a while loop:

Node q = null;
while (q != null && q.item >= 0) {
q = q.next;
}
```

Exercise B

1. Write a loop which will advance a pointer p to point to the 100th node in a list (don't worry about an error if the list is too short);
2. Write a loop which will point successively to the 1st, 3rd, 5th, etc. node in the list; first write it assuming the list has an odd number of nodes, and then write it so that it will never generate an error even if the list has an even number of nodes.

### Basic Paradigms for Modifying a List (Example: deleting a node)

Chaining down a list is often combined with some kind of modification of the structure of the list, for example, you might want to insert or delete a node. We will consider node deletion as an example to illustrate the basic problem with a singly-linked list: a list goes in one direction, and you can't go backwards!

Suppose you want to delete the node pointed to by `p` in the following list:

The problem is that to delete the -1, you need to "reroute" the pointer in the node containing 4 "around" the -1 so that it points to the node containing 7:

But you don't have a pointer to the node containing 4! The simplest solution is just to keep a "trailing pointer" q that follows p as it chains along, always pointing to the node before p:

```

```
Now, to delete the -1, we can simply perform the following to "reroute" the next pointer in q to point to the node after p:
```
q.next = p.next;

```

This general technique is sometimes called the "inchworm" since the movement of the two pointers is like the way an inchworm moves its body.

```        Node p = head;
Node q = null;
while( p != null ) {         // During first iteration, p points to first element and q has no value;
// thereafter, p points to a node and q points to the previous node
q = p;
p = p.next;
}

// OR, using a for loop:

for(Node  p = head, Node q = null; p != null; q = p, p = p.next ) {
// During first iteration, p points to first element and q has no value;
// thereafter, p points to a node and q points to the previous node
}

```
But it is a little bit complicated! What if we want to delete the first node? What if the list is empty? These are the special cases that make iterative algorithms a bit messy (we'll introduce a technique to avoid some special cases in the next section). For example, to delete the first node in the list containing a negative number, we could do the following:
```   void deleteNegative() {
if( head == null)             // Case 1: List is empty, do nothing
;
else if( head.item < 0 )      // Case 2: have to delete first node?
else {                        // Case 3: Don't have to delete first node, so can use inchworm

Node p = head.next;         // p points to second node
Node q = head;              // q points to first node
while( p != null ) {
if( p.item < 0 ) {
q.next = p.next;
break;
}
q = p;                   // chain along, and keep q trailing p
p = p.next;
}
}
}

// OR, using a for loop:

void deleteNegative() {
if( head == null)              // Case 1: List is empty, do nothing
;
else if( head.item < 0 )      // Case 2: have to delete first node?
else {                        // Case 3: Don't have to delete first node, so can use inchworm

for(Node p = head, Node q = null; p != null; q = p, p = p.next ) {
if( p.item < 0 ) {
q.next = p.next;
break;
}
}
}
}    ```

In general, the Inchworm technique is the easiest way to manage this problem, so we will use it in the rest of these notes. However, be careful about those special cases! In general, we have to worry about the following cases when modifying a linked list:

1. The list is empty;
2. The modification takes place at the beginning of the list (e.g., you are inserting a node at the front, or deleting the first node);
3. The modification takes place at the end of the list; and
4. The modification takes place somewhere in the middle.

### Accessing the end of the list: Maintaining a "last" pointer

Although in a simple linked list, you need to go through the entire sequence to get to the last node, when you need to routinely access the end of the list (e.g., successively adding to the end of the list), it is useful to maintain a pointer to the last node.

Here is a simple method which uses a global definition of a pointer to the last node:

```     Node head = null;
Node last = null;

if(head == null) {                      // if head is null, then must initialize last pointer
}
else {
last.next = new Node(n,null);
last = last.next;              // chain along to update last pointer to new last node
}
}

```

You may have noticed that you have seen this algorithm before: addToEnd is the same as enqueue(...) for a queue....

### Generalizing Linked-List Methods for Arbitrary Lists

The deleteNegative example showed that it is often messy to deal with the special cases involving a global head pointer. Even worse, we have to have access to the exact head variable inside the method, so you would have to write a method like this for each list (i.e., you can't just write one method to be used on all such lists).

The simple solution to this is of course to parameterize the head pointer in the methods. The head pointer is made a parameter to the method, and the (possibly) new head pointer is returned as the result of the method. A few examples will clarify this important technique, which we will make extensive use of.

Supposing that we do not need to make any changes to the list, then we simply rewrite our methods to take the head pointer as a parameter:

```    int length(Node h) {
int len = 0;
for(Node p = h; p != null; p = p.next ) {
++len;
}
return len;
}

// To use:

```

Compare this with the version first presented above!

If we need to modify the head pointer, then we return the necessary value through the method. Here is a new version of addToFront using this technique:

```  Node addToFront(int n, Node h) {
return new Node(n, h);
}

// How to use it:

```

Often this technique will remove some messy special cases. For example, the previous algorithm to delete the first negative number in a list could now we written as:

```     Node deleteNegative(Node h) {
if(h == null) {          // only special case now
return null;
}
else {
Node p = h.next;         // p points to second node
Node q = h;              // q points to first node
while( p != null ) {
if( p.item < 0 ) {
q.next = p.next;
break;
}
q = p;                   // chain along, and keep q trailing p
p = p.next;
}
}
}

// to use it:

```

This technique can still be used when the head pointer is a global field in the ADT. We will make consistent use of this idiom in the "cookbook" of iterative algorithms below, and also in our recursive algorithms. It is a powerful technique and you should try to use it whenever possible.

Exercise C

1. What changes do we have to make to the delete method just show if we want to delete ALL instances of a given number?
2. Write a method, using the inchworm technique, which returns true if there is place in the list where there is a number immediately followed by the same number (e.g., a node contains a 5 and points to another node containing a 5);
3. Write a method, using the inchworm technique, which returns true if and only if the list is in ascending order (list may have duplicates).

## Iterative Algorithms for Linked Lists

We now present a "cookbook" of a number of useful iterative algorithms. Other algorithms can usually be created by suitably modifying one of these. Throughout we will use the idea that the head pointer is made a parameter to the method, and the (possibly) new head pointer is returned as the result of the method.

### Print the List (repeated from above)

```  void printList() {
for(Node p = head; p!=null; p = p.next) {
System.out.print(p.item + " -> ");
}
System.out.println(".");
}  ```
You would call the method like this:
```    printList(head);
```

### Finding the length of a list (repeated from above)

```
int length(Node h) {
int count = 0;
for(Node p = h ; p!=null; p = p.next)
++count;
return count;
}
```

### Member

This next function is a standard one; it returns a `true` or `false` depending on whether the number is in the list:

```  boolean member(int n,Node h) {
for(Node p = h; p != null; p = p.next )
if( p.item == n )
return true;
}

```

### Looking up a item

This is a variation of the previous: it returns a pointer to the node containing a number, or null if it is not in the list:

```  Node find(int n,Node h) {
for(Node p = h; p != null; p = p.next )
if( p.item == n )
return p;
}

```

### Deleting an item in a list

Here is a version of delete which removes the first instance only of a specific number from the list; as observed above, the complication is that we have a number of special cases, depending on where the node to be deleted is.

```   Node delete(int n, Node h) {
if(h == null)           // case 1: list is empty, do nothing
return null;
else if(h.item == n)
return h.next;      // case 2: item to delete is the first node
else {                  // case 3: find the node before n using the inchworm technique
for(Node p = h.next, q = h; p != null ; q = p, p = p.next ) {
if( p.item == n ) {
q.next = p.next;
return h;   // return original head pointer, since it does not change
}
}
}
}

// You would call the method like this:```
`    head = delete(23,head); `

### Inserting an item into a sorted list

We have shown above how easy it is to insert an item into the first position using the `Node()` constructor; inserting into a sorted list (in ascending order) is quite similar to the delete algorithm and again uses the two-pointer technique. In this algorithm we will use a while loop just to show how that works, as compared with the for loop.

```  Node insertInOrder(int n, Node h) {
if(h == null)                 // case 1: list is empty -- add to front and return pointer to new first node
return new Node(n,h);
else if(h.item >= n)          // case 2: n should be before the first node  -- again add to front
return new Node(n, h);
else {                        // case 3: find the node before where n should be using the inchworm technique
Node p = h.next;
Node q = h;
while( p != null ) {
if(p.item >= n) {               // found insertion point, between p and q
q.next = new Node(n, p);
return h;                   // since first node did not change, return original head pointer
}
q = p;                          // chain along!
p = p.next;
}
q.next = new Node(n, null);   // case 4: Node must be added at end of list
}
}

// You would call this as follows:

```

### Copying a List

The technique here is to simply chain down a list, making a copy of each node, and adding to the end of a new list:

```  Node copyList(Node h) {
Node p = h;
if(p == null)                   // Case 1: list is empty
return null;
else {                          // Case 2: list has at least one node
Node q = new Node(p.item);    //    put first node in place in copy
Node last = q;                // Maintain a pointer to the last node to facilitate adding to the end of the list
p = p.next;
while( p != null ) {
last.next = new Node(p.item);
last = last.next;           // chain along original list and with the last node in new list
p = p.next;
}
return q;
}
}

// You would call this as follows:
```

### Reversing a list in place

This algorithm is probably one of the most difficult for linked lists; it uses three references which chain down the list together and rearrange the pointers so that node q, instead of pointing to p, now points to r; doing this for each node reverses the entire list. This was a standard exam question on the PhD Qualifying Exam at UPenn when I was a student there..... I've also heard that it is a common interview question at software companies!

```    Node reverse(Node h) {
if(h == null)
return null;
Node p = h.next,  q = h,  r;
while ( p != null ) {
r = q;         // r follows q
q = p;         // q follows p
p = p.next;   // p moves to next node
q.next = r;   // link q to preceding node
}
h.next = null;
return q;
}

// to use:

```

### Reversing a list (by creating a new list)

Here is another solution to the previous problem, but creating a new list is much easier: we think of the new list as a stack, and just push new nodes on it as we go down the input list:

```    Node reverse2(Node h) {
if(h == null)
return null;
Node q = null
for(int p = h; p != null; p = p.next) {
q = new Node(p.item, q);
}
return q;
}```
```
```

Exercise E

1. Modify the delete method so that it deletes every instance of a given integer (hint: this is harder than it looks---make sure that it works on a list where the two instances are right next to each other!);
2. Write a method `arrayToLinkedList(...)` which takes an array of integers and creates a linked list with the same elements in the same order;
3. Write a method `equalLists(...)` which takes two lists and determines if they are identical (have the same elements in the same order);

## Eliminating a Messy Special Case: Linked Lists with Header Nodes (OPTIONAL)

The special cases 1 and 2 in these algorithms, when you need to worry about whether you need to change the head pointer, causes significant problems:

You have to write these special cases into the algorithms, as we have seen above; and

You must write a separate method for EACH linked list, as the pointer head must be explicitly mentioned in the algorithm.

This latter problem is really the most important, as it makes us write multiple versions of the same code, which, as we saw in the case of generics, is a real problem. We would like to write ONE method which can be used for all such lists. This will be solved elegantly when we use recursion, but we can solve the problem in the iterative case by using a dummy first node that contains no value (or a sentinel value, such as Integer.MIN_VALUE) as a item. In this case, you would initialize your list using:

```        Node head = new Node();
```

Alternatively, and sometimes very usefully, we can use the header node to store useful information such as the length of the list. The general outline of a `for` loop which chains down a list keeping a training pointer is now as follows. (We will show the differences from the previous methods in red -- you will see the the differences are usually quite minimal!)

```        for(Node  p = head.next, q = head; p != null; q = p, p = p.next ) {
// During first iteration, p points to first element and q to the header node;
// thereafter, p points to a node and q points to the previous node
}```
For example, if we want to eliminate the first node in our list which contains a negative number, we would write the following:
```       for(Node  p = head.next, q = head; p != null; q = p, p = p.next ) {
if( p.item < 0 ) {
q.next = p.next;
break;
}
```
You do not HAVE to use such a dummy header node, especially if you are not modifying the lists; when you are inserting or deleting nodes, however, they make your life simpler. In any case, they are unnecessary for recursive algorithms, as we shall see.

We now present the same algorithms in versions which assume a global head variable, and header node, as discussed above. They take the head pointer as a parameter, so that they can be used on multiple lists.

### Print the List

```    void printList()  {
for(Node p = head.next ; p != null; p = p.next )
System.out.println(p.item);
}
```
You would call the method like this:
```    printList();
```

### Finding the length of a list

```
int length() {
int count = 0;
for(Node p = head.next ; p!=null; p = p.next) {
++count;
}
return count;
}

You would call the method like this:```
`    int n = length();  `

### Looking up a item

```    Node lookup(int n) {
for(Node p = head.next; p != null; p = p.next )
if( p.item == n )
return p;
}

You would call the method like this:```
`    Node q = lookup(34);  `

### Deleting an item in a list

Now we will see the big advantage of the header node technique: the header node removes cases 1 and 2, and only case 3 remains! The resulting algorithm is much simpler. In addition, you can now delete all instances of a given node by simply removing one line from the code!
```   void delete(int n ) {
for(Node p = head.next, q = head; p != null ; q = p, p = p.next )
if( p.item == n ) {
q.next = p.next;
return;              // if you delete this line it will remove all instances of the number
}
}

You would call the method like this:```
```    delete(head,23);
```

### Inserting an item into a sorted list

Again, the algorithm is simpler, since cases 1 and 2 are gone!
```
void  insertInOrder( int n ) {
Node p = head.next;                   // p points to first real node in list
Node q = head;                        // q trails p
while( p != null ) {
if(p.item >= n) {               // found insertion point, between p and q       -- This is case 3
q.next = new Node(n, p);
return;
}
q = p;
p = p.next;
}
q.next = new Node(n, null);        // Node must be added at end of list    --- This is case 4
}

You would call the method like this:```
```    insertInOrder(23);
```

### Reversing a list

```    void reverse() {
if(head.next == null)                  // empty list
return;
while ( p != null ) {
r = q;         // r follows q
q = p;         // q follows p
p = p.next;   // p moves to next node
q.next = r;   // link q to preceding node
}