CSC236 Data Structures - Linked Lists

Linked Lists

Arrays are built in to most programming languages. An array:

has a fixed size, determined when the array is created.
all elements in an array are the same type.
allows direct access to any element, using the subscript.

Linked list are built dynamically, so they get bigger and smaller as needed. They do not provide direct access to every element. In a linked list there is no subscript for an element, instead, each linked list element refers or points to the next element in the list. Thus we will see that there are some programs that are more efficient using linked lists while others are more efficient using arrays.

LLNode Class

To create a linked list we need a node to hold each list element. A node is an object with two fields: one to hold the element being stored, and one to point to the next element:

public class LLNode<T> {
   protected T info;
   protected LLNode<T> link;
   .
   .
   .
}

This looks similar to recursion but the link doesn't mean that a node points to itself; it means that the node points to an object of the same type. Here is a picture of an array of Strings and the same elements stored in a linked list. With a linked list we create a new node to hold each element added to the list, and then we set the link fields to make the nodes point to each other. Then we can use the link fields to move from one node to the next.

The constructor initializes the info field and sets the link field to null. The other methods are sets and gets.

The LLNode Class

We must create a new node for each element in a list, and the nodes must be linked together. We must always have a reference to the first node in the list, otherwise we lose track of the nodes at the beginning of the list. Subsequent nodes can be found by following the links.

Practice

Given the following list, show what the list will look like after each of the following. Start with the original list each time.

head.setLink(ptr);
head.setInfo(ptr.getInfo());
ptr = ptr.getLink();
head.getLink().setLink(ptr.getLink());
ptr.setLink(ptr);
head.getLink().getLink().setLink(head);

Traversal

There are a number of operations which require visiting all nodes in the list: print all values, update all values, or search the list for a particular value. Remember we never change the reference that points to the first node, so we need another reference to move through the nodes on the list. Let's call this reference curr. Then the code looks like:

set curr to point to first node {
while curr is still pointing to a node
   visit the node (print it, update it, ...)
   move curr to the next node
}

Suppose "visit" the node means print the info field. Then our code would look like:

If we are writing a method for a class, then we need this code to work for every list: a list that is empty, has one node, or has many nodes.

Insertion

There are several different cases for inserting into a list: inserting at the beginning, in the middle, or at the end of the list. At this time we will only cover inserting at the beginning of the list.

To insert, we need to create a new node to hold the element being added to the list, and then we need to link it in. To link it, we need to make the new node point to the former first node, and make head point to the new node. Note that to create the new node we need another reference. This picture shows the changes needed to add a node containing the value "east" to the front of the list:

make newnode point to a new node containing the value east
make newnode's link point to the same node as head
make head point to the same node as newnode

This would make our code look like:

As with traversal, we need to make sure that the insert works on an empty list, a list with one node, and a list with multiple nodes. Look at the insert code and see if it works for all of these cases.