• (3 Pages)
  • +
  • 1
  • 2
  • 3

Linked List Tutorial Rate Topic: ****- 3 Votes

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10395
  • View blog
  • Posts: 38,462
  • Joined: 27-December 08

Post icon  Posted 03 December 2009 - 08:50 AM

*
POPULAR

Linked Lists are an alternative to ArrayLists that Computer Scientists have come up with. While an ArrayList uses an array internally to store the data, a LinkedList uses nodes to hold the elements. These nodes then point to each other, thus leading to the name "Linked" List. There are three types of Linked Lists: singly-linked lists, doubly-linked lists and circularly-linked lists. Singly-linked lists work by having each node pointing to the next node, with the tail node (or end node) pointing to nothing (or a null reference). Doubly-linked lists expand upon the singly-linked list, with each node pointing to the previous node as well as the next node. In doubly-linked lists, both the head node (first node) and the tail node point to nothing. Circularly-linked lists expand upon the singly-linked list differently than the doubly-linked list; instead of having the tail node pointing to nothing, it "circles" back around, pointing to the head element as the name suggests.

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.

Is This A Good Question/Topic? 13
  • +

Replies To: Linked List Tutorial

#2 skaoth  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 91
  • View blog
  • Posts: 601
  • Joined: 07-November 07

Posted 23 January 2010 - 09:49 PM

I've read some portions of this tutorial and have found some minor issues:


1) You should decrement the size of the list when removing items to be consisten with add.
2) Your node class defines a elem field but the LinkedList class uses element.
3) public void add(E elem) does not work when adding the first. After adding
the first item to the list, tail should be pointing to head.

public void add(E elem) {
		//if we don't have any elems in our LinkedList
	if (head == null) {
		head = new Node<E>();
		head.element = elem;
		tail = head;
		head.next = tail;
	} else {
		tail.next = new Node(); //add a new node to the end of the list
		tail = tail.next; //set the tail pointer to that node
		tail.element = elem; //set elem to be stored to the end node
	}
	counter++;
}



4) public E remove(int index) removes the wrong element. The element
removed from the list is (index + 1). Calling LinkedList.remove(0), removed the value 1 instead
of 0.

Here is the test code that I used and output of my test
[output]
0 1 2 3 4 5 6 7 8 9
removed: 1
0 2 3 4 5 6 7 8 9

Exception in thread "main" java.lang.Assertionerror
at test.Main.main(Main.java:45)
Java Result: 1
[/output]

	public static void main(String[] args) {
		LinkedList<Integer> ll = new LinkedList<Integer>();

		for(int i = 0; i < 10; i++) {
			ll.add(i);
		}

		assert(ll.size() == 10);
		ll.print();


		Integer v = ll.remove(0);
		System.out.println("removed: " + v);
		ll.print();
		assert(ll.size() == 9);
	}



Here is the LinkedList implementation. The only change from
this tutorial is with inserting the nodes and a print function

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 void print() {
		for (Node n = head; n != null; n = n.next) {
			System.out.print(" " + n.element.toString());
		}
		System.out.println("");
	}

	public int size() {
		return counter;
	}

	public void add(E elem) {
		//if we don't have any elems in our LinkedList
		if (head == null) {
			head = new Node<E>();
			tail = head;
			head.element = elem;

			head.next = tail;
		} else {
			tail.next = new Node(); //add a new node to the end of the list
			tail = tail.next; //set the tail pointer to that node
			tail.element = elem; //set elem to be stored to the end node
		}
		counter++;
	}

	public E remove(int index) {
		assert (index >= 0 && index < size()); //force valid index
		temp = head; //start at the beginning of the list

		//iterate to the position before the index
		for (int i = 0; i < index; 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.element; //store the element to return
		two = null; //remove the node
		return elem; //return the element at that position
	}
}


Was This Post Helpful? 4
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10395
  • View blog
  • Posts: 38,462
  • Joined: 27-December 08

Posted 25 January 2010 - 09:16 AM

My mistakes. Thanks for catching. :)
Was This Post Helpful? 2
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10395
  • View blog
  • Posts: 38,462
  • Joined: 27-December 08

Posted 11 February 2010 - 07:07 AM

My tutorial has been edited and revised to fix the mistakes pointed out by Skaoth, thanks to OliveOyl.
Was This Post Helpful? 0
  • +
  • -

#5 Metropoler  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 78
  • Joined: 29-December 09

Posted 17 February 2010 - 01:10 PM

I always want to write a tutorial and I thought: Nobody has already written one about dynamic lists. But well, it's already out. Too bad that I am always too late :-/

But good tutorial! +1 rep
Was This Post Helpful? 0
  • +
  • -

#6 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 894
  • View blog
  • Posts: 3,153
  • Joined: 12-May 09

Posted 17 February 2010 - 03:40 PM

Sweet. You should do one on skiplists =p
Was This Post Helpful? 0
  • +
  • -

#7 sandm0nkey  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 21-January 10

Posted 17 February 2010 - 07:23 PM

Okay, everything you had on adding, removing, and getting elements in linked lists was a great help. But how would I cycle a linked list? Like if I needed to take the first element and move it to the end? Would it need to do something like "get the first element and store it in a variable (or something like it)" and then "add the variable at the end"? Or would that leave the spot that the first element was in still there?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10395
  • View blog
  • Posts: 38,462
  • Joined: 27-December 08

Posted 18 February 2010 - 07:39 PM

@Metropoler: You could always write one on dynamic arrays.

@sandm0nkey: Why don't you add(remove(0))? The remove(0) call will remove and return the first elem, then the add() method will add it to the end.
Was This Post Helpful? 0
  • +
  • -

#9 m-e-g-a-z  Icon User is offline

  • Winning
  • member icon


Reputation: 496
  • View blog
  • Posts: 1,453
  • Joined: 19-October 09

Posted 28 April 2010 - 06:35 PM

Could of had an isEmpty boolean method returning head==null, apart from that, very nice tutorial!
Was This Post Helpful? 0
  • +
  • -

#10 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2870
  • View blog
  • Posts: 11,021
  • Joined: 15-July 08

Posted 29 April 2010 - 01:16 PM

I have to tell you. I learned A LOAD from this tutorial. Thanks.

I have some comments that I'd like to make here, some additions and some small fixes - let's start with a potential addition. First, I think you ought to make an explicit addition of a toString() method. Most will try to print out the array in this fashion:

for (int i = 0; i < ll.size(); i++) {
    System.out.println(ll.get(i));
}



Though it looks fine, at the core, this is O(n^2) as the get method is O(n) as opposed to ArrayList's O(1). However, the ArrayList print method is O(n), and by making a toString(), so can a LinkedList. Basically, this will only traverse the array once, not each index times each index, making it O(n).
Edit: didn't notice that was a comment. May want to stick it in the tutorial body.
	public String toString() {
		String s = "[";
		temp = head;
		for (int i = 0; i < size(); i++) {
			if (i != size()-1)
				s+=temp.elem + ", ";
			else
				s+=temp.elem;
			temp = temp.next;
		}
		s+="]";
		return s;
	}



Next, I noticed two actual problems. The first is in the get() method. I ran the system and sure enough, it always grabbed one index too far:

Quote

[1, 4, 7, 3, 56, 12]
get(4) returned 12
get(0) returned 4
[get(5) returned] NullPointerException [(Should be legal)]


Here is what you have:
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

}



Personally, I changed the assert too, but that's a matter of style. What NEEDS to be changed is the <=. It needs to be <.

Same problem with the add(int index, E elem) method. It adds the node one too far. See?
		System.out.println(ll);
		ll.add(2, new Integer(7)); // Not necessary to make Integer. Done for clarity.
		ll.add(0, new Integer(8)); // Not necessary to make Integer. Done for clarity.
		System.out.println(ll);



Results in:

Quote

[1, 6, 4, 3]
[1, 8, 6, 4, 7, 3]


See? Let's fix it more. Here's what you have:
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()-1){
        add(elem);
        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; 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;

}



Again, your error is simple. for(int i = 0; i < index; i++)/[il] needs to be [il]for(int i = 0; i < index-1; i++)

So...simple errors aside, you did a marvelous job on this tutorial! I hope you and the mods will consider editing it in the way that I have outlined.
Was This Post Helpful? 2
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10395
  • View blog
  • Posts: 38,462
  • Joined: 27-December 08

Posted 01 May 2010 - 02:55 PM

Tutorial updated to correct minor errors. Thanks to everyone who is constantly helping me improve my tutorial! :)
Was This Post Helpful? 1
  • +
  • -

#12 prateek_g  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 4
  • Joined: 27-July 10

Posted 28 July 2010 - 05:00 AM

There is some cases that you haven't considered while writing the add(int i,E elem) method.
First of all the case when index supplied is 0.
In this case, the head pointer have to be modified.

Secondly,
When we are using add(index, elem) method, we expect the result something like this:
Whatever is there at indexth postion is shifted at (index+1)th position and the new element is passed and placed at indexth position.

But when the index supplied is equal to (size-1), then you call the add(Elem) method which just appends the element at the end of the list.According to standard output, the element should have been placed at (size-1)th position and the element at (size-1)th position should have been shifted to sizeth position.

I rewrote the code
Here:
public E addElem(E e,int index)
	{
		if(index ==0)
		{
			node<E> newNode = new node<E>();
			newNode.elem = e;
			newNode.next = head;
			head = newNode;
			this.size++;
		}
		else
		{
			temp = head;
			for (int i=0; i<index-1 ; i++)
			{
				 temp = temp.next;
			}
			node<E> newNode = new node<E>();
			newNode.next = temp.next;
			newNode.elem = e;
			temp.next = newNode;
			this.size++;
		}

		return e;
	}



I tested it.
It is running fine in all the cases:
When the index supplied is 0.
When the index supplied is between 0 and size-1.
When the index supplied is size-1.
I hope you will review the changes and edit the post.
:)

This post has been edited by prateek_g: 28 July 2010 - 05:17 AM

Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10395
  • View blog
  • Posts: 38,462
  • Joined: 27-December 08

Posted 28 July 2010 - 05:38 AM

Updating the minor fix for index = 0, and the size()-1 bug. Thanks for pointing that out. :)
Was This Post Helpful? 0
  • +
  • -

#14 prateek_g  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 4
  • Joined: 27-July 10

Posted 28 July 2010 - 06:03 AM

Same problem also exist with remove(elem) and remove(index) method.
They dont consider border cases which involve updating head and tail pointer.

I rewrote the code and tested it for all possibilities. :)
Here is the code for these two functions:
	public E remove(int index)
	{
		temp = head;
		int i;
		E e_temp;
		
		if(index == 0)
		{
			e_temp = head.elem;
			head = head.next;
		}
		else if(index == size-1)
		{
			e_temp = tail.elem;
			for (i=0; i<size-2; i++)
			{
				temp = temp.next;
			}
			tail = temp;
			tail.next = null;
		}
		else
		{
			for (i=0; i<index-1; i++)
			{
				temp = temp.next;
			}
			e_temp = temp.next.elem;
			temp.next = temp.next.next;
		}
		this.size--;
		return e_temp;
	}



	


	public E remove(E e)
	{
		temp = head;
		int i;
		E e_temp;
		boolean flag= false;
		node<E> temp2=head;

		for (i=0; i<size; i++)
		{
			if(temp.elem.equals(e))
			{
				flag = true;
				break;
			}
			temp2 = temp;
			temp = temp.next;
		}
		if (flag == true)
		{
			if (i ==0)
			{
				e_temp = head.elem;
				head = head.next;
				this.size--;
				return e_temp;
			}
			else if (i == size-1)
			{
				e_temp= tail.elem;
				tail = temp2;
				tail.next = null;
				this.size--;
				return e_temp;
			}
			else
			{
				temp2.next = temp.next;
				this.size--;
				return temp.elem;
			}
		}
		else
		{
			return null;
		}

	}



And by the way, very nice tutorial.
did a decent job.
I enjoyed it :)
Was This Post Helpful? 1
  • +
  • -

#15 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10395
  • View blog
  • Posts: 38,462
  • Joined: 27-December 08

Posted 03 August 2010 - 09:47 PM

Adjusted to account for more conditions. Thanks for pointing those out. And glad you enjoyed the tutorial. :)
Was This Post Helpful? 2
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3