CODEWITHSUNDEEP
javalinked-list
Shobosy
Shobosy

Reputation: 50

Can someone explain a few lines about Linked List in Java?

I'm currently studying for a test and I don't really understand linked list that well. I was wondering if anyone could explain a few lines of code to me. 

class Node{
  Node next, previous;
    final int value;
  Node(int v){
    value = v;
  }
}

public class Linked{
  Node start = null, end = null;
  // Add a node on the end
  void append(int v){
    Node n = new Node(v);
    if (start == null){
      start = end = n;
      return;
    }
    end.next = n;
    n.previous = end;
    end = n;
  }
// Add a node to the front
void prepend(int v){
  Node n = new Node(v);
  if (start == null){
    end = start = n;
    return;
  }
  n.next = start;
  start.previous = n;
  start = n;
 }
}

The lines that I need explained are the last 3 lines in the append and the prepend methods. The comments explain the purpose of each of the methods, but I don't understand what is actually being done in those lines of code. Thanks in advance.

Upvotes: 1

Views: 97

Answers (4)

Asaf Savich
Asaf Savich

Reputation: 653

Imagine as if you have a chain, every part (node) of the chain knows only the one in front of it and the one behind it. So, now i want to append new part (node) to the end of the chain, we'll call it N.
A --> B --> C ===> A --> B --> C --> N.
In order to insert N properly i need N to know C is behind it and C to know N is in front of it. So, now i'll update c.next or in your case end.next to be N and n.previous to be end. And now my new ending is N and not C.

Same thing goes for the start.

A --> B ==> N --> A --> B We'll updated A, N and start.

Upvotes: 0

matt
matt

Reputation: 12346

You are going to create a new node that will be after the tail, end of the list.

end.next = n;

Likewise, since it is doubly linked, n will now have a previous node end.

n.previous = end;

And finally since the new node is now the tail of the list we assign it to end.

end = n;

Prepend follows the similar logic. The previous head, start is going to come after the new node.

n.next = start;

Since it is doubly linked, start needs to know that the previous node is the new node.

start.previous = n;

Finally, our new node is the new head.

start = n;

Upvotes: 0

almostcolin
almostcolin

Reputation: 59

The class Node shows that there are items in the list called nodes. These items keep track of the item before and after the current node (next and previous). The Linked class creates a Node object for the start and end of the list and has two methods: append will add an integer, v, to after the current node and prepend will add an integer to the node before the current node.

Upvotes: 0

Eran
Eran

Reputation: 394106

append

When you wish to add a node at the end of the list, it should be linked to the current last node :

end.next = n; // the current last node points to the new node
n.previous = end; // the new node points back to the previous node 
                  // (which is the current last node)
end = n; // the new node becomes the last node

prepend is similar :

n.next = start; // the node that follows the new node is the current first node
start.previous = n; // the previous node of the current first node is the new node
start = n; // the new node becomes the first node

Upvotes: 3

Related Questions