You are all familiar with the use of arrays to keep a set of elements in memory. There are many good things about arrays--they allow us to randomly access cells, thats vital in some applications, addressing cells is also easy since each cell has a nice numeric address and each comes after the other. There are applications where we need dynamic space allocation and that is why we introduce you to linked lists.
Here are few reasons for why arrays might not meet our storage needs perfectly:
Linked lists can be implemented with arrays, but typically in languages like Java that support dynamic allocation, they are not. You can create cells as you need them, and can remove them when you wish. But, you don't have a nice numeric address like you do with arrays. The address of cells are NOT in sequence nicely like they are in arrays, in fact, we don't refer to them as cells, we call them nodes. You have to get each element of the sequence to remember the address of the next. In the object oriented paradigm, we say that each node keeps a reference to the next node. sometimes, we design our nodes to even keep a reference to a previous node, we refer to linked lists with such nodes as doublely-linked lists. Other times we design the linked list, so that the last node points to the first one. Such linked lists are referred to as circular linked lists. Linked lists are a tremendous asset. We add nodes as we need to, we can put a node between two other nodes by changing their references. In java, we can delete a node by simply making their previous node reference their next node, if we have a doublely linked list, their next node will now reference their previous node also. Java's Garbage Collector will collect any space that is left unreferenced. So, by simply not referencing a node we have effectively deleted it.
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 first look at the definition of a singlely linked list. Notice that
it is as if a node can be inside another node. Such recursive definitions
are common for linked lists. Also notice the constructor, it is designed
to allow for setting both the data part of the node and the reference
to the next node. The last thing you should notice lack of a qualifier
like private or public. This simply means that
Node is accessible in the package that it sits in. So, for example
if we design a Node class as part of the stringQueue
package we get to use it to create nodes in our dynamicStringQueue
class which is in the same package. More about this later.
class Node {
dataType element;
Node next;
Node (Node n, dataType e) {
next=n;
element=e;
}
}
Here is a graphical image of what the linked lists would look like, if
we were simply holding some numeric values:
10 ---> 20 ---> 30 ---> 40 --->||
Here is the definition of a doublely linked list, note that we have an
additional reference to a node (prev).
class Node {
dataType element;
Node next;
Node prev;
Node (Node n,Node p, dataType e) {
next=n;
prev=p;
element=e;
}
}
Here is a graphical image of what a doublely 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,10);
In this statement we are making head reference a newly created
node that will contain 10 with the nextreference as null.
of course, we are assuming that our dataType is int and that we
are using the first Node class shown above. It should be obvious
that we can't have two classes with the same name, so, if we need two node
classes in a package, we need to name them differently.
Consider the following list of elements with head referencing the
node that contains 10:
10 ---> 20 ---> 30 ---> 40 --->||
head
Lets examine a few statements and see what happens to the list:
head.element=12;
12 ---> 20 ---> 30 ---> 40 --->||
head
head.next.element=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. Sorry about the crude graphics.
Node temp=new(head.next,17);
12 ---> 25 ---> 30 ---> 40 --->||
head ^
|
17
temp
The following statement, effectively, adds temp's node to the list.
head.next=temp;
12 ---> 17 ---> 25 ---> 30 ---> 40 --->||
head temp
temp.next=temp.next.next; //remove the node that contains 25!
12 ---> 17 ---> 30 ---> 40 --->||
head temp
As you may be able to tell, you gain incredible flexibility when you
implement a queue with a linked list. Let us consider dynamicStringQueue class.
First of all, it uses a doublely linked list which means the second
Node class shown above is utilized. Note that two
reference variables are used to keep track of both front of the list and
the back of the list, first and last. This will facilitate
easy insertion and deletions for our queue. Both variables start as
null so the constructor doesn't have any code. Just checking
last or first against null should determine if
if queue is empty. You will find that full always returns
false as you can't get full in this implementation. Lets take a
careful look at enqueue and dequeue.
public void enqueue(String x) {
if (first==null) {
first=new Node(null,null,x);
last=first;
}
else {
last.next=new Node(null,last,x);
last=last.next;
}
}
We first check for first being null, that helps us figure out
if we need both first and last set, or we only need to add
a new node to the end of the list. The statement
first=new Node(null,null,x);
sets first to reference
a newly created node. This new node will contain the new value in it with
both its prev and next node references set to null. Note
that last gets to reference the same node as first does.
When there are elements already in the list, we create a new node that we
place after last. This new node will have a pre node reference
that will be set to last. Here is what happens when we enqueue mark:
last=last.next makes last
reference the new node. Consider the following list:
||<--- jones <---> fair <---> mary <---> leo --->||
first last
||<--- jones <---> fair <---> mary <---> leo <---> mark --->||
first last
Let use consider dequeue:
public String dequeue() {
Node old_first=first;
if (first == last) {
first= null;
last= null;
}
else {
first=first.next;
first.prev=null;
}
return old_first.element;
}
Node old_first=first; allows us to remember the reference
to the node in front of the queue, since the manipulations that follow
will effectively take that node out of the list. If the node in front
of the queue is the last node in the queue, we set both first
and last to null. Otherwise, we just make the node right after
first, the first node by saying
first=first.next;
. We then
use the statement first.prev=null; to set this newly appointed
first node's prev variable to null. Now only old_first
references the old first node. Once we return the element in the node
referenced by old_first this node can be garbage collected.