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

## Linked List Tutorial Rate Topic:     4 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=143089&amp;s=293bdb7230d442d94d0c737712e6a708&md5check=' + ipb.vars['secure_hash'], cur_rating: 5, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08 Posted 03 December 2009 - 08:50 AM POPULAR

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> tail = null;
private Node<E> temp = null;

private int counter = 0;
public int size(){return counter;}
}

```

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
head = tail = new Node<E>();
}
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()){
return;
}

else if(index == 0){
Node<E> temp = new Node<E>();
temp.elem = elem;
counter++;
return;
}
/*Here, we start to see the temp node come into play.
We use it to track the current node without modifying
*/
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());

//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
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){
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;

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? 14

## Replies To: Linked List Tutorial

### #2 skaoth Reputation: 91
• 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.
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
} 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

at test.Main.main(Main.java:45)
Java Result: 1
[/output]

```	public static void main(String[] args) {

for(int i = 0; i < 10; 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> tail = null;
private Node<E> temp = null;
private int counter = 0;

}

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;
}

//if we don't have any elems in our LinkedList

} 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
}
}

```

### #3 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08

Posted 25 January 2010 - 09:16 AM

My mistakes. Thanks for catching. ### #4 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,863
• 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.

### #5 Metropoler Reputation: 2
• 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

### #6 xclite • • I wrote you an code
•   Reputation: 1419
• Posts: 4,270
• Joined: 12-May 09

Posted 17 February 2010 - 03:40 PM

Sweet. You should do one on skiplists =p

### #7 sandm0nkey Reputation: 0
• 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?

### #8 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,863
• 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.

### #9 m-e-g-a-z Reputation: 497
• Posts: 1,457
• 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!

### #10 Dogstopper Reputation: 2972
• Posts: 11,223
• 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 = "[";
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());

//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){
return;
}

/*Here, we start to see the temp node come into play.
We use it to track the current node without modifying
*/
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.

### #11 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,863
• 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! ### #12 prateek_g Reputation: 2
• 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;
this.size++;
}
else
{
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

### #13 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,863
• 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. ### #14 prateek_g Reputation: 2
• 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)
{
int i;
E e_temp;

if(index == 0)
{
}
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)
{
int i;
E e_temp;
boolean flag= false;

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)
{
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 ### #15 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,863
• 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. • (3 Pages)
• • 1
• 2
• 3

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; } 