• Post Reply Bookmark Topic Watch Topic
  • New Topic

How does the LinkedList increase?  RSS feed

 
Ranch Hand
Posts: 226
Eclipse IDE Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For the arrayList once overcome the initial capacity it creates a new array on background. What about the linkedList? How is it actually implemented in terms of structure?
I know it's unbounded, and so the ArrayList is. I just would like to know the mechanism beneath the LinkedList.
Thanks in advance.

 
Marshal
Posts: 4052
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would recommend doing an internet search for "Linked List". There are many many articles out there that explain it quite comprehensively.

Start with https://en.wikipedia.org/wiki/Linked_list
 
Nick Widelec
Ranch Hand
Posts: 226
Eclipse IDE Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So basically the limit of a LinkedList is the memory itself.. Ok cool and you are superright that with any further internet search I would have found the answer. Sorry about that. You can close the topic as far as I am concerned.
 
Tim Cooke
Marshal
Posts: 4052
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nick Widelec wrote:So basically the limit of a LinkedList is the memory itself

Exactly, yes. It's a nice way to use only the memory you need to store items in a list that is likely to vary in size over time. The trade off is the overhead of having to store on each item the address of the next item (and the last item for a Doubly Linked List).
Nick Widelec wrote:Sorry about that

Not a problem. Glad you found what you needed.

There is a "Resolved" button you can click to indicate that you've got your answer.
 
Ranch Hand
Posts: 514
1
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello!

Internally LinkedList uses instances of its private inner class Node.
And frankly I did not meet any limitations on adding new elements into LinkedList !
When you add new element into LinkedList new Node is created and its item variable points to your reference which you store in LinkedList.
As you know LinkedList is implementation of doubly-linked list.
So every Node there has also refrence to Node on the left and to the right.
Adding new elements to LinkedList sequentially is very quick. Most LinkedList does is to create new Node instance, link it to previous inserted Node at that end!

However be watchful if you want to add new element to LinkedList by index it might be quite long operation especially if index is close to the middle of collection and your collection is large.

Removing elements from the end sequnetially is extremely fast. Again removing by index depends how index is close to any end of collection.
You may use removeFirstOccurrence(Object o) or removeLastOccurrence(Object o) if you know at which end (head or tail) your Object o is present.

Finally I encourage to look through my tutorial on LinkedList that explores thoroughly Internal Life of LinkedList
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!