University of Toronto
Department of Computer Science
csc 148: Introduction to Computer Science

Linked Data Structures

With references we can create many different kinds of data structures by linking components together. The linked list data structure is one of the simplest. A linked list is a set of objects where each object has a reference field that can point to any object in the set. We always keep a reference to the beginning of the list. We can make the list grow or shrink by adding or deleting objects.

A particularly useful kind of linked list is one that is sorted. In this tutorial, you will learn about linked lists by writing a method to insert elements into a sorted linked list.

Insertion in a sorted linked list

We first need the definition of a class for constructing nodes of the linked list:

 
          class Node {
              int key;
              Node link;
          }

We can now create objects of class Node to construct our linked list. Note that key does not necessarily need to be an integer. We use integers here for simplicity. A node might contain other members depending on the purpose of the linked list.

Now before we can design an insertion method, we must think about what it means to insert an element into a linked list. In other words we need the specifications for insert.

Specifications

The method insert will take a key as a parameter, will create a new node object to hold the key, and will add the new object to the linked list pointed to by head such that the list remains ordered.

Here is the header for the linked list class and the insert method.

   public class LinkedList {
      Node head;

      public insert(int key) {
          Node current = head;
         // The rest of the method will go here.
      }
   }

Step 1: Traversing the list

First, let's write a loop to go down the linked list to the end. (We'll later modify it to stop at the right point for insertion.)

We are going to use the local variable current to keep track of where we are in the list.

What Java statement lets us advance current from one node in the list to the next?

We will use a while loop to advance current repeatedly, thus traversing the whole list.

        while( /* condition */ ) {
             // body of the loop
        }

What condition will be true while we are traversing the list and false when we get to the end of the list?

When you have answered the two questions above, you may proceed to the next step.

Previous | Home | Next