Posted 03 December 2009 - 08:50 AM
In this tutorial series, we will be exploring the basic concepts of singly-linked lists through the implementation of key methods from the List interface including add(elem), add(index, elem), set(index, elem), get(index), get(elem), remove(index), remove(elem), and indexOf(elem), as well as hitting on certain points for doubly and circularly-linked lists.
Let's start out by examining a basic Linked Node. It looks simple enough, and in reality, the individual nodes aren't that complex. When dealing with singly-linked list, the Node previous doesn't come into play. It becomes more important however, when working with doubly and circularly-linked lists.
public class Node<E>{
E elem;
Node<E> next, previous;
}
So let's start defining our LinkedList class. So far, we see only 3 Nodes and a constructor. As we covered earlier, the head node is the first element in the list and the tail node is the last. The temp node, however, will come in handy when we have to iterate through our list. Lastly, we use the counter field to store the number of elements contained in the list so as to make the size() method more efficient, with an O(1) vs. an O(n) if the counter field wasn't used.
public class LinkedList<E>{
private Node<E> head = null;
private Node<E> tail = null;
private Node<E> temp = null;
private int counter = 0;
public LinkedList(){}
public int size(){return counter;}
}
The add(elem) method
When dealing with the individual methods() of LinkedLists, it is helpful to think of them in relation to only two or
three Nodes- the one being affected, the one before it (applicable only to doubly and circularly linked lists) and
the one after it.
As we can see, the add() method, which simply appends an element to the end of the list, is pretty
straight-forwardfor a singly-linked list. We simply add the element and update the tail node so that the new node is at the end of the list.
public void add(E elem){
//if we don't have any elems in our LinkedList
if(head == null){
head = tail = new Node<E>();
head.elem = elem;
head.next = tail;
tail = head;
}
else{
tail.next = new Node<E>(); //add a new node to the end of the list
tail = tail.next; //set the tail pointer to that node
tail.elem = elem; //set elem to be stored to the end node
}
counter++;
}
Consider this- In a doubly-linked list, you would have to also deal with making sure the impacted Nodes are adjusted for not only pointing to the next element in the list, but the previous element as well. How would you accomplish this, and how might it impact runtime?
The add(index, elem) methodThis method is designed to add the specified element at a given position in the list. When working with arrays, this is pretty straight-forward. However, with LinkedLists this becomes more complicated. Due to the nature of LinkedLists, there is no efficient indexing system. Instead, you have to iterate the collection to find the position for which to add the element. From there, it becomes the same concept as the add(elem) above though you have to deal with the new element being sandwiched between two other nodes instead of at the end. Let's try it:
public void add(int index, E elem){
/*If the user wants to add it to the end of the list
call the other add() method, which is more efficient
and then end this method*/
if(index == size()){
add(elem);
return;
}
else if(index == 0){
Node<E> temp = new Node<E>();
temp.elem = elem;
temp.next = head;
head.previous = temp;
head = temp;
counter++;
return;
}
/*Here, we start to see the temp node come into play.
We use it to track the current node without modifying
the head node.
*/
temp = head;
for(int i = 0; i < index-1; i++) temp = temp.next; //move to the next node
Node<E> myNode = new Node<E>(); //create a new node
myNode.elem = elem; //and set the elem
myNode.next = temp.next; //set it to point to the next elem
temp.next = myNode; //set the previous elem to point to it
counter++; //increment the count;
}
Consider this- In a singly-linked list, we must start at the beginning and work forward. However, this becomes a problem if the index is closer to the end of the list, then why do we need to start at the beginning of the list? Wouldn't be more efficient to start at the end? With doubly-linked lists, we keep track of the previous as well as the next Nodes, so we can start at the tail of the list and work backwards.
The get(index) method
This method is similar to the add(index, elem) method in the sense that we have to iterate through the LinkedList to return the proper element. Unlike arrays, LinkedLists do not allow for an easy method of indexing. So let's give it a try:
public E get(int index){
//forces the index to be valid
assert (index >= 0 && index < size());
temp = head; //start at the head of the list
//iterate to the correct node
for(int i = 0; i < index; i++) temp = temp.next;
return temp.elem; //and return the corresponding element
}
The get(elem) and indexOf(elem) methods
This method works identically to the indexOf(elem) method, which we will cover in this section as well. In fact, we will make a call to indexOf(elem) when the get(elem) method is called. In a nutshell, the indexOf(elem) method uses the same process of iteration throughout the list as do the above methods.
So let's start off with these methods
//returns first index of the given elem
//returns -1 if elem not found
public int get(E elem){
return indexOf(elem);
}
public int indexOf(E elem){
temp = head; //start at the beginning of the list
int i = 0; //create a counter field that isn't local to a loop
//while we haven't found the elem we are looking for, keep looking
for(; !(temp.element).equals(elem) && temp != null; i++)
temp = temp.next;
if(i == size()) return -1; //if the elem wasn't found, return -1
return i; //otherwise, return the index
}
The remove(index) and remove(elem) methods
If you look back to the add(index, elem) methods, then you will see that when we added elements to the list, we had to make sure we adjusted the pointer of the previous Node to point to the new element, and we had to make the new element point to the next Node. The remove() methods work in the exact opposite manner. Instead of correcting the pointers to account for an extra Node, we want the pointers to act as though it didn't exist.
So let's get started with the remove methods:
public E remove(int index){
assert(index >= 0 && index < size()); //force valid index
temp = head; //start at the beginning of the list
if(index == 0){
E elem = head.elem;
head = head.next;
counter--;
return elem;
}
else if(index == size()){
E elem = tail.elem;
tail = tail.previous;
counter--;
return elem;
}
//iterate to the position before the index
for(int i = 0; i < index-1; i++) temp = temp.next;
Node<E> two = temp.next;
//set temp.next to point to the Node next to the Node to be removed
temp.next = two.next;
E elem = two.elem; //store the element to return
two = null; //remove the node
counter--; //decrement size
return elem; //return the element at that position
}
public E remove(E elem){
temp = head; //start at the beginning of the list
Node<E> two = null;
if(head.elem.equals(elem)){
head = head.next;
head.previous = null;
counter--;
return elem;
}
else if(tail.elem.equals(elem)){
tail = tail.previous;
tail.next = null;
counter--;
return elem;
}
//while the elem hasn't been found but there is another node
while(temp != null && !temp.elem.equals(elem)){
two = temp; //have a reference to the element before the one to remove
temp = temp.next; //in this method, temp will be the elem to remove
}
//if the element wasn't found, return null
if(temp == null) return null;
two.next = temp.next;
E spare = temp.elem; //return element
temp = null;
counter--; //decrement size
return spare;
}
Consider this- How could we improve the efficiency by using a doubly-linked list? For the remove(index) method, we could start at the end of the list and iterate backwards. This would improve the average-case efficiency of the remove(index) method to O(n/4) instead of O(n/2).
Consider this- How would the remove() methods be affected when implementing a circularly-linked list? What would we have to factor in when removing the head or tail elements? We would actually be able to use basically the same process as removing an non-end element in a singly or doubly-linked list.
MultiQuote
| 