CSC 241- Set #7

Example with linked lists

We discussed linked lists initially in Set#5; we then looked at example of them in in dynamicStack and dynamicQueue. It is time to go back to them and see some of the flexibility that one gains by employing them.

Picture a node as an object that has two parts. One part containing data, as many pieces as needed, and one or more references to other nodes. We will look at the definition of a doubly-linked list. Just like dynamicStack and dynamicQueue, it is as if a node can be inside another; such recursive definitions are common for linked lists in Java. Also notice that the constructor is designed to allow for setting both the data part of the node and the reference to the next node and previous. The last thing you should notice is the lack of a qualifier like private or public. This simply means that Node is accessible in the package that it belongs to.

class Node {
   Object element_;
   Node next_;
   Node prev_;
   Node (Node n,Node p, Object e) {
     next_=n;
     prev_=p;
     element_=e;
   }
}

Here is a graphical image of what a doubly linked list would look like, if we were simply holding some numeric values:

||<--- 10 <---> 20 <---> 30 <---> 40 --->||

When implementing any variation of linked lists, you must have a reference to at least one node in the list.

Node head=null;

In this statement we are declaring a variable head which is set to null. null is a value in java that means empty and we use it when setting or checking reference variables. Consider head as a variable that holds a reference to an object of class Node, of course, it is null at this point.

head=new Node(null,null,new String("10");

||<--- 10  --->||
      head

Suppose we build up our list to look like the following:

||<--- 10 <---> 20 <---> 30 <---> 40 --->||
      head

Lets examine a few statements and see what happens to the list. Keep in mind that you can only reference components of a node in the same package as the Node class. Applications that reside outside the package that Node resides in can not perform these instructions.

head.element_=new String("12");

||--- 12 <---> 20 <---> 30 <---> 40 --->||
 head


head.next.element=new String("25");

||--- 12 ---> 25 ---> 30 ---> 40 --->||
     head

Create a new node referenced by temp. This node will contain 17 with its next field set to what head's next is and its prev to head itself. Sorry about the crude graphics.

Node temp=new(head.next,head,new String("17"));  

||--- 12 <---> 25 <---> 30 <---> 40 --->||
     head     
      ^        ^
      |        |
       ---17---
         temp

The following statements, effectively, add temp's node to the list.

head.next=temp;  
temp.next.prev=temp;

||--- 12 <---> 17 <---> 25 <---> 30 <---> 40 --->||
     head     temp

Lets remove the node that contains 25!

temp.next=temp.next.next; 
temp.next.prev=temp;
         
||--- 12 <---> 17 <---> 30 <---> 40 --->||
     head     temp