Doubly linked list insert front method

Question

Completed my hw and I got it wrong. I do not understand why.

For my insert front I do the following.

head.next.prev = newNode; 
newNode.next = head;
newNode.prev = null;
head.prev = newnode;
head.next.prev = head; 
size++;

But instead the solution looks like this following

head.next.prev = newNode(item, head, head.next); // newNode(item,prev,next); So basically head.next.prev is pointing to a newnode here newnode.prev = head and newnode.next = head.next. Ok that make sense. 
head.next = head.next.prev; // huh?
size++;

to me the solution doesn't make sense and my solution is perfectly logical. If you make head.next.prev = a new node, you should make head.next.prev = head, or else there will be a jump right? Also head.next = head.next.prev; doesn't make any sense. That line is basically saying head.prev is pointing to the head itself. Shouldn't it be head.next.prev = head;?

Can anyone point out what's going on? i know the format between the solutions is different but i'm more interested in the logic

The complete code is shown below

There's a lot of confusion. So here's how head is declared

 public class DList {

/**
 *  head references the sentinel node.
 *  size is the number of items in the list.  (The sentinel node does not
 *       store an item.)
 *
 *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
 */

protected DListNode head;
protected int size;

/* DList invariants:
 *  1)  head != null.
 *  2)  For any DListNode x in a DList, x.next != null.
 *  3)  For any DListNode x in a DList, x.prev != null.
 *  4)  For any DListNode x in a DList, if x.next == y, then y.prev == x.
 *  5)  For any DListNode x in a DList, if x.prev == y, then y.next == x.
 *  6)  size is the number of DListNodes, NOT COUNTING the sentinel,
 *      that can be accessed from the sentinel (head) by a sequence of
 *      "next" references.
 */

/**
 *  newNode() calls the DListNode constructor.  Use this class to allocate
 *  new DListNodes rather than calling the DListNode constructor directly.
 *  That way, only this method needs to be overridden if a subclass of DList
 *  wants to use a different kind of node.
 *  @param item the item to store in the node.
 *  @param prev the node previous to this node.
 *  @param next the node following this node.
 */
protected DListNode newNode(Object item, DListNode prev, DListNode next) {
return new DListNode(item, prev, next);
}

/**
 *  DList() constructor for an empty DList.
 */
public DList() {
head = newNode(null, head, head);
head.next = head;
head.prev = head;
size = 0;
}



    public insertfront(Object item){
???????????}

//////////////////// below is the DlistNoe.java

  public class DListNode {

  /**
   *  item references the item stored in the current node.
   *  prev references the previous node in the DList.
   *  next references the next node in the DList.
   *
   *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
   */

  public Object item;
  protected DListNode prev;
  protected DListNode next;

  /**
   *  DListNode() constructor.
   *  @param i the item to store in the node.
   *  @param p the node previous to this node.
   *  @param n the node following this node.
   */
  DListNode(Object i, DListNode p, DListNode n) {
    item = i;
    prev = p;
    next = n;
  }
}

Im something that im not getting.. you never refresh your head value — nachokk
– nachokk, Commented Feb 26, 2014 at 22:27

vanza · Accepted Answer · 2014-02-26 22:23:24Z

2

There's a lot wrong with your insertion code. Just read it in English:

head.next.prev = newNode;

Point the first node's "prev" to the new node (ok)

newNode.next = head;

Point the new node's "next" to the head (what?)

newNode.prev = null;

Point the new node's "prev" to null (it's the first node, so it should point to head)

head.prev = newnode;

Point the head's "prev" to null (you're inserting at the front so you shouldn't be touching this)

head.next.prev = head;

Point the first node's prev to head (undoing what you did in the first step)

So now you have a head that's still pointing to the old first element, and is not pointing back to the last element of the list anymore. And a new element that is not fully inserted (its "prev" is not pointing at anything, and its "next" is pointing at the wrong element).

Yeah, not really correct, I'd say. If you read the correct solution like the above, hopefully you'll see it makes more sense.

answered Feb 26, 2014 at 22:23

vanza

9,9132 gold badges34 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user3345510 Over a year ago

I thought head is the first node. So why newNode.next = head; is not ok? if I insert front isn't newnode suppose to be the first node and isn't the next item = head? And isn't head.prev = the new node you created?

vanza Over a year ago

You can have a linked list with a head (where the head is not an element of the list) or without; I'm assuming since you're using the word "head", that it's the former case (and the correct solution you posted points at that). If you're thinking of the latter case (no head in the list), your code is still not correct, but for different reasons.

WillfulWizard · Accepted Answer · 2014-02-26 23:00:15Z

1

The trouble with structures like linked lists is that when you start modifying references, you lose which nodes are which.

So, let's name some nodes.

The linked list before insertion:

H -> A -> B -> C
H.next = A
H.prev = null
A.next = B
A.prev = H
And so on...

The Goal linked list:

H -> N -> A -> B -> C
H.next = N
H.prev = null (unchanged)
A.next = B (unchanged)
A.prev = N
N.next = A
N.prev = H

Based on the DList invariants and the given solution, there is a head node that does not hold a value that stays the head.

Then let's step through your code:

head.next.prev = newNode; // H.next -> A, A.prev = N. This seems fine.
newNode.next = head;      // N.next = H. What? This doesn't match our goal.
newNode.prev = null;      // N.prev = null. Also doesn't match our goal.
head.prev = newnode;      // H.prev = n. Also doesn't match our goal.
head.next.prev = head;    // H.next -> A, looks like you mean this to be N, but its still A.
                          // thus A.prev = H. Also doesn't match our goal.
size++;

Finally, let's look at the given solution.

head.next.prev = newNode(item, head, head.next);
// First the function, H.next -> A, so...
// N.prev = H. Matches goal.
// N.next = A. Also matches goal.
// Then the assignment:
// head.next -> A, A.prev = N. Matches goal.    
head.next = head.next.prev;
// head.next -> A, A.prev -> N, H.next = N. Matches goal.
size++;

And thus, all 4 changed references have been set.

edited Feb 26, 2014 at 23:00

answered Feb 26, 2014 at 22:25

WillfulWizard

5,4192 gold badges22 silver badges15 bronze badges

2 Comments

WillfulWizard Over a year ago

I don't recall a reason to have an empty head node, so I really would have expected the goal list to be N->H->A->B->C but I can't make sense of the given solution any other way.

WillfulWizard Over a year ago

Looked at your edits, the DList invariants specify no nulls for the nodes that hold value, giving a reason to have a head node with no vale.

Collectives™ on Stack Overflow

Doubly linked list insert front method

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related