ICOM 4035 – Data Structures
Laboratory 3: Linked Lists Data Structures
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
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).
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.