9.4. Linked Lists¶

9.4.1. Linked Lists¶

In this module we present one of the two traditional implementations for lists, usually called a linked list. The linked list uses dynamic memory allocation, that is, it allocates memory for new list elements as needed. The following diagram illustrates the linked list concept. Here there are three nodes that are “linked” together. Each node has two boxes. The box on the right holds a link to the next node in the list. Notice that the rightmost node has a diagonal slash through its link box, signifying that there is no link coming out of this box.

Because a list node is a distinct object (as opposed to simply a cell in an array), it is good practice to make a separate list node class. (We can also re-use the list node class to implement linked implementations for the stack and queue data structures. Here is an implementation for list nodes, called the Link class. Objects in the Link class contain an element field to store the element value, and a next field to store a pointer to the next node on the list. The list built from such nodes is called a singly linked list, or a one-way list, because each list node has a single pointer to the next node on the list.

Java
Java (Generic)

class Link {         // Singly linked list node class
  private Object e;  // Value for this node
  private Link n;    // Point to next node in list

  // Constructors
  Link(Object it, Link inn) { e = it; n = inn; }
  Link(Link inn) { e = null; n = inn; }

  Object element() { return e; }                  // Return the value
  Object setElement(Object it) { return e = it; } // Set element value
  Link next() { return n; }                       // Return next link
  Link setNext(Link inn) { return n = inn; }      // Set next link
}

The Link class is quite simple. There are two forms for its constructor, one with an initial element value and one without. Member functions allow the link user to get or set the element and link fields.

1 / 3 Settings

<<<>>>

Here is a graphical depiction for a linked list storing five integers. The value stored in a pointer variable is indicated by an arrow "pointing" to something. A NULL pointer is indicated graphically by a diagonal slash through a pointer variable's box. The vertical line between the nodes labeled 23 and 10 indicates the current position (immediately to the right of this line).

Saving...

Server Error
Resubmit

9.4.1.1. Why This Has Problems¶

There are a number of problems with the representation just described. First, there are lots of special cases to code for. For example, when the list is empty we have no element for head, tail, and curr to point to. Implementing special cases for insert and remove increases code complexity, making it harder to understand, and thus increases the chance of introducing bugs.

1 / 7 Settings

<<<>>>

Another problem is that we have no link to get us to the preceding node (shown in yellow). So we have no easy way to update the yellow node's next pointer.

head

curr

tail

curr

tail

Saving...

Server Error
Resubmit

9.4.1.2. A Better Solution¶

Fortunately, there is a fairly easy way to deal with all of the special cases, as well as the problem with deleting the last node. Many special cases can be eliminated by implementing linked lists with an additional header node as the first node of the list. This header node is a link node like any other, but its value is ignored and it is not considered to be an actual element of the list. The header node saves coding effort because we no longer need to consider special cases for empty lists or when the current position is at one end of the list. The cost of this simplification is the space for the header node. However, there are space savings due to smaller code size, because statements to handle the special cases are omitted. We get rid of the remaining special cases related to being at the end of the list by adding a “trailer” node that also never stores a value.

The following diagram shows initial conditions for a linked list with header and trailer nodes.

null

head

curr

tail

Here is what a list with some elements looks like with the header and trailer nodes added.

null

head

curr

tail

Adding the trailer node also solves our problem with deleting the last node on the list, as we will see when we take a closer look at the remove method’s implementation.

9.4.1.3. Linked List Implementation¶

Here is the implementation for the linked list class, named LList.

Java
Java (Generic)

import java.util.NoSuchElementException;

// Linked list implementation
class LList implements List {
  private Link head;         // Pointer to list header
  private Link tail;         // Pointer to last element
  private Link curr;         // Access to current element
  private int listSize;      // Size of list

  // Constructors
  LList(int size) { this(); }     // Constructor -- Ignore size
  LList() { clear(); }

  // Remove all elements
  public void clear() {
    curr = tail = new Link(null); // Create trailer
    head = new Link(tail);        // Create header
    listSize = 0;
  }
  
  // Insert "it" at current position
  public boolean insert(Object it) {
    curr.setNext(new Link(curr.element(), curr.next()));
    curr.setElement(it);
    if (tail == curr) tail = curr.next();  // New tail
    listSize++;
    return true;
  }
  
  // Append "it" to list
  public boolean append(Object it) {
    tail.setNext(new Link(null));
    tail.setElement(it);
    tail = tail.next();
    listSize++;
    return true;
  }

  // Remove and return current element
  public Object remove () throws NoSuchElementException {
    if (curr == tail) // Nothing to remove
      throw new NoSuchElementException("remove() in LList has current of " + curr + " and size of "
        + listSize + " that is not a a valid element");
    Object it = curr.element();             // Remember value
    curr.setElement(curr.next().element()); // Pull forward the next element
    if (curr.next() == tail) tail = curr;   // Removed last, move tail
    curr.setNext(curr.next().next());       // Point around unneeded link
    listSize--;                             // Decrement element count
    return it;                              // Return value
  }

  public void moveToStart() { curr = head.next(); } // Set curr at list start
  public void moveToEnd() { curr = tail; }          // Set curr at list end

  // Move curr one step left; no change if now at front
  public void prev() {
    if (head.next() == curr) return; // No previous element
    Link temp = head;
    // March down list until we find the previous element
    while (temp.next() != curr) temp = temp.next();
    curr = temp;
  }

  // Move curr one step right; no change if now at end
  public void next() { if (curr != tail) curr = curr.next(); }

  public int length() { return listSize; } // Return list length


  // Return the position of the current element
  public int currPos() {
    Link temp = head.next();
    int i;
    for (i=0; curr != temp; i++)
      temp = temp.next();
    return i;
  }
  
  // Move down list to "pos" position
  public boolean moveToPos(int pos) {
    if ((pos < 0) || (pos > listSize)) return false;
    curr = head.next();
    for(int i=0; i<pos; i++) curr = curr.next();
    return true;
  }

  // Return true if current position is at end of the list
  public boolean isAtEnd() { return curr == tail; }

  // Return current element value.
  public Object getValue() throws NoSuchElementException {
    if (curr == tail) // No current element
      throw new NoSuchElementException("getvalue() in LList has current of " + curr + " and size of "
        + listSize + " that is not a a valid element");
    return curr.element(); 
  }

  // Check if the list is empty
  public boolean isEmpty() { return listSize == 0; }
}

import java.util.NoSuchElementException;

// Linked list implementation
class LList<E> implements List<E> {
  private Link<E> head;      // Pointer to list header
  private Link<E> tail;      // Pointer to last element
  private Link<E> curr;      // Access to current element
  private int listSize;      // Size of list

  // Constructors
  LList(int size) {      // Constructor -- Ignore size
    this(); 
  }
  LList() { 
    clear(); 
  }

  // Remove all elements
  public void clear() {
    curr = tail = new Link<E>(null); // Create trailer
    head = new Link<E>(tail);        // Create header
    listSize = 0;
  }
  
  // Insert "it" at current position
  public boolean insert(E it) {
    curr.setNext(new Link<E>(curr.element(), curr.next()));
    curr.setElement(it);
    if (tail == curr) {
      tail = curr.next();  // New tail
    }
    listSize++;
    return true;
  }
  
  // Append "it" to list
  public boolean append(E it) {
    tail.setNext(new Link<E>(null));
    tail.setElement(it);
    tail = tail.next();
    listSize++;
    return true;
  }

  // Remove and return current element
  public E remove () throws NoSuchElementException {
    if (curr == tail) {// Nothing to remove
      throw new NoSuchElementException("remove() in LList has current of " + curr + " and size of "
        + listSize + " that is not a a valid element");
    }
    E it = curr.element();                  // Remember value
    curr.setElement(curr.next().element()); // Pull forward the next element
    if (curr.next() == tail) {
      tail = curr;   // Removed last, move tail
    }
    curr.setNext(curr.next().next());       // Point around unneeded link
    listSize--;                             // Decrement element count
    return it;                              // Return value
  }

  public void moveToStart() { 
    curr = head.next(); // Set curr at list start
  } 
  public void moveToEnd() {      
    curr = tail; // Set curr at list end
  }

  // Move curr one step left; no change if now at front
  public void prev() {
    if (head.next() == curr) {
      return; // No previous element
    }
    Link<E> temp = head;
    // March down list until we find the previous element
    while (temp.next() != curr) {
      temp = temp.next();
    }
    curr = temp;
  }

  // Move curr one step right; no change if now at end
  public void next() { if (curr != tail) { curr = curr.next(); } }

  public int length() { return listSize; } // Return list length


  // Return the position of the current element
  public int currPos() {
    Link<E> temp = head.next();
    int i;
    for (i=0; curr != temp; i++) {
      temp = temp.next();
    }
    return i;
  }
  
  // Move down list to "pos" position
  public boolean moveToPos(int pos) {
    if ((pos < 0) || (pos > listSize)) {
      return false;
    }
    curr = head.next();
    for(int i=0; i<pos; i++) { curr = curr.next(); }
    return true;
  }

  // Return true if current position is at end of the list
  public boolean isAtEnd() { return curr == tail; }

  // Return current element value. Note that null gets returned if curr is at the tail
  public E getValue() throws NoSuchElementException {
    if (curr == tail) // No current element
    {
      throw new NoSuchElementException("getvalue() in LList has current of " + curr + " and size of "
        + listSize + " that is not a a valid element");
    }
    return curr.element(); 
 }
  
  //Tell if the list is empty or not
  public boolean isEmpty() {
    return listSize == 0;
  }
}

1 / 7 Settings

<<<>>>

Let's look at the data members for class LList.

class LList implements List {
private Link head; // Pointer to list header
private Link tail; // Pointer to last element
private Link curr; // Access to current element
private int listSize; // Size of list

Saving...

Server Error
Resubmit

1 / 5 Settings

<<<>>>

Now we look at the constructors for class LList.

// Constructors
LList(int size) { this(); } // Constructor -- Ignore size
LList() { clear(); }
// Remove all elements
public void clear() {
curr = tail = new Link(null); // Create trailer
head = new Link(tail); // Create header
listSize = 0;
}

Saving...

Server Error
Resubmit

1 / 9 Settings

<<<>>>

The linked list before insertion. 15 is the value to be inserted.

// Insert "it" at current position
public boolean insert(Object it) {
curr.setNext(new Link(curr.element(), curr.next()));
curr.setElement(it);
if (tail == curr) tail = curr.next(); // New tail
listSize++;
return true;
}

null

head

curr

tail

Saving...

Server Error
Resubmit

Here are some special cases for linked list insertion: Inserting at the end, and inserting to an empty list.

1 / 16 Settings

<<<>>>

Here is an example showing insertion at the end of the list. 15 is the value to be inserted.

// Insert "it" at current position
public boolean insert(Object it) {
curr.setNext(new Link(curr.element(), curr.next()));
curr.setElement(it);
if (tail == curr) tail = curr.next(); // New tail
listSize++;
return true;
}

null

head

curr

tail

Saving...

Server Error
Resubmit

9.4.2. Linked List Remove¶

1 / 7 Settings

<<<>>>

Now we look at the remove method.

// Remove and return current element
public Object remove () throws NoSuchElementException {
if (curr == tail) // Nothing to remove
throw new NoSuchElementException("remove() in LList has current of " + curr + " and size of "
+ listSize + " that is not a a valid element");
Object it = curr.element(); // Remember value
curr.setElement(curr.next().element()); // Pull forward the next element
if (curr.next() == tail) tail = curr; // Removed last, move tail
curr.setNext(curr.next().next()); // Point around unneeded link
listSize--; // Decrement element count
return it; // Return value
}

null

head

curr

tail

Saving...

Server Error
Resubmit

1 / 10 Settings

<<<>>>

Finally, we will look at how a few other methods work.

null

head

curr

tail

temp

curr

Saving...

Server Error
Resubmit

Implementations for the remaining operations each require $\Theta(1)$ time.

OpenDSA Data Structures and Algorithms Modules Collection

Chapter 9 Linear Structures

9.4. Linked Lists¶

9.4.1. Linked Lists¶

9.4.1.1. Why This Has Problems¶

9.4.1.2. A Better Solution¶

9.4.1.3. Linked List Implementation¶

9.4.2. Linked List Remove¶