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

Linked Data Structures

We can create many different kinds of data structures by linking components together using references. The linked list data structure is one of the simplest. A linked list is a set of objects in which each object has a reference field that points to the next object. We always keep a reference to the beginning of the list. Below is an example of a linked list of integers.

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 for inserting an element 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 out of which to construct our linked list. Note that key does not necessarily need to be an integer, and that there can be additional data in each node, 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

Specifications for method insert: The method 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 sorted in non-decreasing order. (Why do we call it "non-decreasing" order rather than simply "increasing order"?)

Here is the header for the insert method, in the context of a linked list class.

   public class LinkedList {
      Node head;

      public void 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 very 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 a single step forward to the next node?

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? (It will become false when we get to the end of the list, thus causing the loop to stop.)

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

Previous | Home | Next