• Post Reply Bookmark Topic Watch Topic
  • New Topic

LinkedList and how is references work?  RSS feed

 
Anton Sotnikov
Ranch Hand
Posts: 59
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well hello everyone!
You know i got difficulties in moment when i am thinking about LinkedList:
There is code:
1. Element of LinkedList - Node


2. LinkedList


3. App



Please explain something of how it works:
1.
In moment when insertAtHead calls a lot of time and occur Node newNode = new Node(data); what does created in memory - many references with same name newNode?

2. What does it means this.head = newNode;

one reference copy value information of object to another reference?

or it a reference that recalls on another reference?

or just two references for one object Node?

after that this.head = newNode - Does newNode didn't terminate?




 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That appears to be a singly‑linked list. Doubly‑linked lists have references to “previous” in each node.

I would suggest you draw some diagrams. You will have something like thisNow draw that sort of diagram in soft pencil but with rectangles representing the Nodes and write value and next inside each rectangle.

Remember that rootNode and topNode are ordinary Node objects; they differ in their position and the “next” reference in the top node points to null. Now let's have a look at the root of the list.When you assign root to something, that ought to represent inserting a new node at the very beginning of the list. So the former root node becomes the 2nd node and the new node becomes root. Without moving any of the other nodes, rub out the pencil arrows to the first node and draw a new node and arrows to that. Now you can see the effects of reassigning root.
When you create a new node you create a Node object which has references to the next node and to the value (and in doubly‑linked lists only, to the previous node).

Now I think you will understand the questions better and be able to answer for yourself.

Note that all the other nodes remain in situ. That is the nice thing about a linked list. You can add nodes in the middle without moving any other nodes. If you have an arrayed list you have to move many nodes to make space for a new node in the middle.
 
Anton Sotnikov
Ranch Hand
Posts: 59
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
is it valid scheme as you said for drawing diagram?
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The first two pictures are essentially the same.

Note that there is no "null" object, just a null value. head and newNode don't point to null, they are null.

The third picture: OK, except for the red crosses. Just making 'head' refer to the new Node object, doesn't automatically make newNode not refer to the same new Node object anymore.
 
Anton Sotnikov
Ranch Hand
Posts: 59
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Just making 'head' refer to the new Node object, doesn't automatically make newNode not refer to the same new Node object anymore.

It means like that:
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!