ICOM 4035 – Data Structures

Fall 2007

 

Laboratory 3: Linked Lists Data Structures

 

1.    Objectives

 

  1. Understand the behavior of a linked list.
  2. Study some implementation alternatives and their behavior.
  3. Implement the different linked list learned.

 

2.    Overview

 

A linked list is a collection of nodes that are liked together in an apparently linear manner. Internally in the computer memory these nodes may be located anywhere across it. What makes these nodes be tied then? The answer to this question is an internal field which points to a reference to the next node in the list. The simplest node has two fields: data and next.

Several nodes tied together become the linked list. At least there must be a field inside the list which points to the first node, called the head, to have then access to the whole list. Other more complex implementations may also have a reference to the last node (tail).

 

 

 

 

 

 

 

 

 

 

Right now you will study the following linked list models:

 

Single Linked List (SLList.java) :- This is the simplest model. It has a reference to the

first node and each node is linked by pointing to the next node only.

 

Single Linked First Last List (SLFLList.java) :- This implementation of the list has

references to both the first and last node. However each node is linked through a pointer to the next node only.

 

Double Linked List (DLList.java) :- This implementation is like the SLFLList except that

the nodes are linked doubly, meaning they point to the next node as well to the

previous one.

 

 

Single Linked Circular List (SLCList.java) :- A special implementation which has no

end. Nodes in this implementation are linked in a circular manner meaning that

the first and last nodes are linked together. Again in memory the nodes don’t need

physically be arranged in a circle, the important thing is that the last node is

connected to the first one. Sometimes it is convenient to create such linked list in

a double linkage manner, this way the list can be circulated forward or backwards.

This implementation is known as Doubly Linked Circular List (DLCList).

 

 

 

 

3.    Practice

 

In this laboratory you are asked to implement the interface ArrayList using a Doubly Linked List (DLList.java). After you may test you code with the file lab3.java. The results should be the same as the ones obtained on lab2.java in the previous lab. Download the source code here.