CODEWITHSUNDEEP
javadata-structureslinked-list
Jason
Jason

Reputation: 11363

Inserting node in a double-linked list

I'm having trouble understanding the second half of connecting a new node into a double-linked list. I'm writing an add method that takes in the node which the new node is to be inserted after. My area of difficulty is understanding how to link to the next node after the previous node links have been re-directed to the new node.

So, here's where I've come up with

Chunk<E> newChunk= new Chunk<E>();

    newChunk.next= prevChunk.next;
    prevChunk.next= newChunk;

    newChunk.prev= newChunk.next.prev;
    newChunk.next.prev= newChunk;

My understanding is since the newChunk.next= prevChunk.next command copies the memory address of prevChunk.next and sets that value into newChunk.next, and then the prevChunk.next is reset to link to the newChunk.

So since the prevChunk is the only node referenced here that is already in the list, and the next fields have been re-routed to the newChunk, am I on the right track in using those references to link to the next node?

Upvotes: 3

Views: 2114

Answers (3)

Kevin Zhou
Kevin Zhou

Reputation: 1283

You are correct, but on a side note, most double linked lists are not circular, as the lastNode's next isn't the firstNode (same with firstNode's prev is not the lastNode). If "prevChunk" were the last Node in the double linked list, and you are adding newChunk after prevChunk as the last item in the linked list, 

NewChunk.prev= newChunk.next.prev;

is essentially setting NewChunk's previous element to null's previous element, which probably isn't what you are going for

You might want to check if previous.next initially is null.

Upvotes: 3

kasgoku
kasgoku

Reputation: 5027

What you have there is correct. However, it is a bit hard to understand(thus your question). Here is a more intuitive solution that should work and be easier to understand for you:

Chunk<E> newChunk = new Chunk<E>();
Chunk<E> nextChunk = prevChunk.next;

prevChunk.next = newChunk;
newChunk.prev = prevChunk;

nextChunk.prev = newChunk;
newChunk.next = nextChunk;

I create a new reference to the next node in the linked list. This might be be as efficient as the last answer because its creating a new reference but should help you understand the solution.

Upvotes: -1

David Watson
David Watson

Reputation: 2039

Something like this should work.

Chunk<E> newChunk= new Chunk<E>();

    newChunk.next = prevChunk.next;
    newChunk.prev = prevChunk;
    prevChunk.next = newChunk;
    newChunk.next.prev = newChunk;

Upvotes: -1

Related Questions