Linked Lists Plus

Complexity Trade-offs

Summary of chapter 6 performance tables.

Head Nodes

Managing the insertion and deletion of the first node is a special case in sorted lists.

The middle and last elements are noted to be similar in management.

The special case of handling the first node can be eliminated by creating a special "head node"

• pre-allocated like a regular node
• store no data in it
• head points to it, and the head node points to the real first element of the list

//constructor code
LLObjectNode head = new LLObjectNode(); //initialize head node in const
head.setInfo(null);

  public void insert (Comparable item)
  // Adds a copy of item to list. 
  {
    LLObjectNode newNode = new LLObjectNode();   // reference to node being inserted
    LLObjectNode prevLoc;                        // trailing reference
    LLObjectNode location;                       // traveling reference

    location = head.getLink();
    prevLoc = head;
    // this variable is removed: 'moreToSearch'

    // Find insertion point.
    while (location != null)  //loop until item is < element
    {
      if (item.compareTo(location.getInfo()) > 0)     // list element is larger than item
      {
        prevLoc = location;
        location = location.getLink();
      }
    }

    // Prepare node for insertion.
    newNode.info(item);

    // Insert node into list.
      newNode.setLink(location);
      prevLoc.setLink(newNode);
    numItems++;
  }

Trade a little space for improvement in program time and simpler programming.

Circular linked list

My preference for circular linked lists is to build upon the notion of a head node (See above). This is a deviation from Dale/Joyce/Weems.

Idea: Rather than having a NULL at the last element, point back to first element.

//Set up initial tight looped list
LLObjectNode head;

    // in constructor
head = new LLObjectNode();
head.setInfo(null);
head.setLink(head);

//No changes to insertion code as w/ head node
//except the search stopping criteria
LLObjectNode prev = head;
LLObjectNode cur = head.getLink(); //get first node

while(cur != head && cur.getInfo().compareTo(newValue)<0){
    prev = cur;
    cur = cur.getLink();
}
....

The above is the algorithm for searching as well.

Doubly Linked Lists

The problem with singly linked lists is that direction of access is limited to one direction. Traversing the list in reverse order is not an option. Access to the end of the list is linear in time. The insertion and removal routines had to maintain an auxiliary variable to perform the updates.

A doubly linked lists maintains two references per node: "next" and "previous". Of course, now, twice as many links have to be maintained.  Reverse order processing is easier.

I also prefer to implement doubly linked lists with the circular concept as well.

public abstract class DoublyLinkedList implements ListInterface

{
  protected class ListNode 
  // Used to hold references to list nodes for the linked list implementation
  {
    protected Comparable info;           // the info in a list node
    protected LLObjectNode next;         // a link to the next node on the list
    protected LLObjectNode prev;         // a link to the previous node on the list  
  }  
  
  protected LLObjectNode head;           // reference to the first node on the list
     protected int numItems;            // Number of elements in the list
  protected LLObjectNode currentPos;     // Current position for iteration

  public LinkedList()
  // Creates an empty list object.
  {
    numItems = 0;
    head = new ListNode();
    head.next = head;
    head.prev = head;
    currentPos = head;
  }

Insertion into a doubly linked list

  public void insert (Listable item)
  // Adds a copy of item to list. 
  {
    ListNode newNode = new ListNode();   // reference to node being inserted
    ListNode prevLoc;                               // trailing reference
    ListNode location;                               // traveling reference
    boolean moreToSearch;

    location = head.next;
    prevLoc = head;
    moreToSearch = (location != null);

    // Find insertion point.
    while (moreToSearch)
    {
      if (item.compareTo(location.info) < 0)     // list element is larger than item
        moreToSearch = false;
      else
      {
        prevLoc = location;
        location = location.next;
        moreToSearch = (location != null);
      }
    }

    // Prepare node for insertion.
    newNode.info = (Listable)item.copy();

    // Insert node into list.
      newNode.prev = location.prev; //1
      newNode.next = location;      //2
      location.prev.next = newNode; //3
      location.prev = newNode;      //4     
 
   numItems++;
  }

Array Implementation of Lists

A linked list could be implemented in an array.

The elements might be stored in an array in any order, and “linked” by their indexes.

We keep a separate list of available nodes.

Tracking free space:

List Applications

Heap storage management

All free segments of memory are kept in a list.  When an object allocation occurs, the free list is searched for a block of contiguous storage that is sufficient for the object.  The excess space is recorded again in the free list. 

When the garbage collector determines that an object is no longer accessible, the space used by the object is placed back into the free list.

There may be times that adjacent blocks of memory are free.  Coalescing allows these adjacent free space blocks to be formed into a larger block.  If not done, the memory will be fragmented to a point that large objects cannot be allocated the necessary space.

Organization of files on disk

The directory space and file information is kept in list type of organization.