1

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.

Improve this question
1
  • The links that hold the list together are chaged to reflect the current state. Commented Apr 7, 2016 at 8:36

4 Answers 4

Reset to default
3

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Improve this answer

Comments

0

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;
Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.