Linked Lists

last updated 2/9/07

Problems with using arrays to keep collections of data

  1. Predefined size, many languages have arrays that are fixed at compile time (static)
    If you choose an array size that is too small, you may need to later increase the array size and recompile the program. Choose an array size that is too large will waste space.
  2. Insertion and deletion of elements to maintain order requires
    - processing time to "make room" or "close the hole"
    - special handling of unused elements

Advantages of array implementation of collections

Linked lists

 


Node organization

Basic element of a linked list is a "record" structure of at least two fields (a class definition with these instance variables).  The object that holds the data and refers to the next element in the list is called a node.

data

next ptr

data component may actually be several fields or instance variables of any complexity

next ptr is a reference to the next element in the structure. There can be multiple reference fields but we won't consider that now.  "pointer"/"reference"/"link" are synonymous in this discussion.


 Head is a reference variable that points to the first element.


Insertion Overview

Three cases of insertion:  at beginning, into middle at end

 

 


Example

insertion of the value 8 into the above list (middle of the list)


 

 

 


Insertion

of the value 2 (at the head/beginning of the list)


 

 

 

 

 


Insertion

of the value 19 (at the tail of the list)


 

 

 

 

 


Deletion

of the value 7

 

 

 

 

 

 


Definition of a node class

Because a linked list is recursive in nature, we need a structure to manage the node as well as the data to be contained in the node.  We will typically use a feature of Java called inner classes (a class that is defined within a class).

  1. Define the instance variables to hold data and refer to the next node in the list.
  2. Define a null node constructor (default).
  3. Define a non-empty node constructor; this requires a link to the next node passed as a parameter

public class LLStringNode 
{
  private String info;
  private LLStringNode link;
  
  public LLStringNode(String info)
  {
    this.info = info;
    link = null;
  }
 
  public void setInfo(String info)
  // Sets info string of this 
  // LLStringNode.
  {
    this.info = info;
  }

  public String getInfo()
  // Returns info string of this 
  // LLStringNode.
  {
    return info;
  }
  public void setLink(LLStringNode link)
  // Sets link of this LLStringNode.
  {
    this.link = link;
  }

  public LLStringNode getLink()
  // Returns link of this LLStringNode.
  {
    return link;
  }
}


 


Creating elements

An empty list:

//not same as the default constructor
LLStringNode aNode = null;

A node containing data but doesn't point to anything; a single node list.

LLStringNode sNode1 = 
new LLStringNode ("basketball");

A list with two elements.

LLStringNode sNode2 = 
new LLStringNode("baseball");
sNode1.setLink(sNode2);

Recommendation: DRAW PICTURES!

 

 

 


Null pointer exceptions

You may have already seen this error.  It arises when you have a reference variable that really isn't referencing anything (as in aNode above).

The code sNode1.getLink().getInfo() returns "baseball".

However, the code sNode2.getLink().getInfo() would throw the null pointer exception.  There is no object to which you can apply the getInfo method.

Often your code will need to check if the reference pointer is not null, as in

if(nodeVar != null){
    //process the data and/or
    //access the next link
}

 

 


Traversing an existing list

When you have a linked list, you often want to traverse or walk the list, visiting every node and somehow processing the data there.  Maybe you want to search the list.


LLStringNode currNode = letters;
while (currNode != null)
{
  System.out.println(currNode.getInfo());
  currNode = currNode.getLink();
}



Searching a linked list

You may search a list for a particular value in the data fields.  This is a variation on the traversal. 

The operation is linear in time.

If you want the i-th element-- you have to traverse as well.  A linked list is NOT a random access structure. Getting any arbitrary node from a linked list costs linear time.  So the time gained in adding or deleting a node (constant time) may be lost in traversing.

   // Search the contents of the structure
   LLStringNode temp = head;      
   while (temp != null && !(temp.getInfo().equals(searchKey)){
      temp = temp.link();
   }
   if (temp != null){ 
      //process found item
   } else {
      //handle situation that is wasn't found
   }

 


Search Function

Putting this into a search function...

// Search the contents of the LL structure
public static LLStringNode searchLL(LLStringNode head, String searchKey){
   while (head != null)
      if(head.getInfo().equals(searchKey)){
         return head;
      }
      head = head.link();
   }
   return null;
}
// Search for i-th node in the list; return null if too short
public static LLStringNode indexLL(LLStringNode head, int position){
   while (position > 0 && head != null)
      head = head.link();
      position--;
   }
   return head;
}


Insertion into a linked list

 

Insertion at beginning is easiest (O(1)).

Create node with new information:
LLStringNode newNode = new LLStringNode("A");

Now set the link variable of the newNode node to point to the beginning of the list :
newNode.setLink(letters);

finish the insertion by setting the letters variable to point to the newNode, making it the new beginning of the list:

letters = newNode;


Insertion into an empty list

--establish first node into list

Same proces as inserting into beginning.

 

Linked List StringLog ADT Implementation

We call our new StringLog class the LinkedStringLog class, to differentiate it from the array-based class of Section 2.3.

We also refer to this approach as a reference-based approach.

The class fulfills the StringLog specification and implements the StringLogInterface interface.

Unlike the ArrayStringLog, the LinkedStringLog will implement an unbounded StringLog.

Instance Variables

LLStringNode log;

In this implementation, the elements of a StringLog are stored in a linked list of LLStringNode objects. We call the instance variable that we use to access the strings log. It will reference the first node on the linked list, so it is a reference to an object of the class LLStringNode.

String name;

Recall that every StringLog must have a name. We call the needed variable name.


Constructor for LinkedStringLog


public class LinkedStringLog implements StringLogInterface 
{
  protected LLStringNode log; // reference to first node of linked 
                              // list that holds the StringLog strings
  protected String name;      // name of this StringLog
  
  public LinkedStringLog(String name)
  // Instantiates and returns a reference to an empty StringLog object 
  // with name "name".
  {
    log = null;
    this.name = name;
  }
  ...
} 

Note that we do not need a constructor with a size parameter since this implementation is unbounded.


The insert operation

//Insert the new string in the front:

public void insert(String element)
// Precondition:   This StringLog is not full.
//
// Places element into this StringLog.
{      
  LLStringNode newNode = new LLStringNode(element);
  newNode.setLink(log);
  log = newNode;
} 

An example use:


LinkedStringLog strLog;
strLog = new LinkedStringLog("Nicknames");
strLog.insert("Babyface");
String s1 = new String("Slim");
strLog.insert(s1);

 

 

 


Clear operation

public void clear()
// Makes this StringLog empty.
{ 
  log = null;
}

All objects (strings, nodes, etc.) that cannot be accessed from reference variables, by following any link internal to the objects are candidates for garbage collection.

 

 


Remaining methods

public boolean isFull()
// Returns true if this StringLog is full, false otherwise.
{              
  return false;
}
public String getName()
// Returns the name of this StringLog.
{
  return name;
}
public int size()
// Returns the number of Strings in this StringLog. O(n)
{
  int count = 0;
  LLStringNode node;
  node = log; //start at beginning of list
  while (node != null)
  {
    count++;
    node = node.getLink(); //follow to next node
  }
  return count;
}
public String toString()
// Returns a nicely formatted string representing this StringLog.
{
  String logString = "Log: " + name + "\n\n";
  LLStringNode node;
  node = log;
  int count = 0;
    
  while (node != null)
  {
    count = count + 1;
    logString = logString + count + ". " + node.getInfo() + "\n";
    node = node.getLink();
  }
  return logString;
}

public boolean contains(String element)
{                 
  LLStringNode node;
  node = log;
  boolean found = false;
  while (node != null) 
  {
    if (element.equalsIgnoreCase(node.getInfo()))  // if they match
      found = true;                                // set flag and
      break;                                       // exit loop
    else
    {
      node = node.getLink();
    }
  }
 return found;
}