9

As far as I know, the concept of a linked list is a bunch of object connected to each other by having a 'next' and sometimes 'previous' attribute to traverse the objects.

I noticed in Java, you can create a LinkedList object...but treat it like an array/list/sequence by using the same methods such as .add(), .get(), etc.

So, is LinkedList internally an array-like sequence?

Improve this question
3

8 Answers 8

Reset to default
13

So, is LinkedList internally an array-like sequence?

No. It's a series of instances of a private nested class Entry, which has next, previous and element references. Note that you could have found this out yourself by looking at the source code, which comes with the JDK.

The reason why this internal structure is not exposed is that it prevents the structure from becoming corrupted and e.g. containing a loop. And the uniform access via the List and Deque interfaces allows polymorphic use.

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

8 Comments

+1: The list which is internally an array-like sequence is called ArrayList. ;)
-1: It depends on your programming skill I guess. From the wikipedia article on Linked Lists: "It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools." -- FYI, memory pools are the arrays that pros use to internally store linked lists. They are also known as slab allocators.
@Anthony: revenge downvote, eh? Get over it. Skilled pros don't get into internet-hairpulling over what level a question should be answered on.
@MichaelBorgwardt Absolutely not. I agree that your answer of "no" is correct in most applications and implementations, but not all. You can actually implement linked-lists with arrays as the underlying data structure, in cases where performance is a concern -- as the wikipedia article says.
@Anthony Blake The question is about the specific implementation of LinkedList class provided by the Java Collection API. An array-based implementation is ArrayList as Peter stated before in his comment here.
|
5

A LinkedList in Java works just as you would expect it to do. If you use the official Collections LinkedList then it will indeed be a a bunch of object connected to each other by having a 'next' and sometimes 'previous'.

And yes, it has a get(int index) method which is surprising because it would not be very efficient as you would need to start at the beginning and count your way up the list to find the indexth entry and this is not what LinkedLists are good at. The reason it is there is because LinkedList implements the List interface. This is something you can with ALL lists.

However, you would probably try to avoid using a LinkedList when most of your access to it is through the get(int index) method as that would clearly be most inefficient. You would be perhaps better to use an ArrayList.

Improve this answer

Comments

4

LinkedList is a chain of entities in which every entity knows about next-one, so get(index) operation requires iterating over this chain with counter. But this list optimized for adding and deleting by position (in case when I need to put element inside list or delete element from middle linked list performs better)

Improve this answer

Comments

2

as i know linkedlist is like what you said in the first paragraph. each object has two references, called it's previous and it's next. unlike array which works sequentially (in C it's exactly stored in sequence. i think java just does the same, that's why we can't re-size an array), list works by referencing. so logically it works slower than array does.

Improve this answer

Comments

1

It is possible to implement an object that works like an array, using a linked list. Compared to arrays, some operations will be faster and some will be slower. For example, calling get() for an element near the end might be quite a lot slower with a linked list than with an array. But, it's still possible.

On the other hand, deleting an element from the middle of a linked list will be faster than the corresponding operation done using arrays.

Improve this answer

Comments

1

Not really. Linked list is provided by the collection and by good design you could create a double linked list. Now it is not like array because these objects will not have indexes and are not elements within the container i.e. list. Hence you go through defining the next and previous and dictate what the next move is. They all have the same methods because again they are collections like i said.

Improve this answer

Comments

0

So, is LinkedList internally an array-like sequence?

NO It is Doubly-linked list implementation.

Improve this answer

Comments

-8

Internally it will be using what is called a 'slab allocator' -- this is basically a linked list of small arrays. Each time you add an object, it checks if there is space in the slab, and if so, puts the object there. Otherwise, it allocates a new slab and puts the object in the first element of the slab.

This technique minimizes memory allocation overheads -- if you add a lot of items to a linked list, that would be a lot of small memory allocations which take a lot of time, and the slab allocators minimize that

Improve this answer

10 Comments

This is simply wrong. Java is not C++. Small allocations are fast. Consequently, the API implementation does not use any tricks to avoid it.
@MichaelBorgwardt Where do you think the JVM gets the memory for each object it allocates? Do you think the JVM is calling malloc() every time? Garbage collectors work with memory in slabs. Please explain how you think Java is allocating memory for linked lists without slabs of memory.
@MichaelBorgwardt From documentation about IBM's JVM: "These sections are typically implemented as contiguous slabs of native memory that are under the control of the Java memory manager (which includes the garbage collector)."
@Anthony Blake Then why do not even go deeper and explain how malloc() works? What JVM implementation do you use as reference? There exist 8 KiB JVMs, too. These are implemented VERY simple. You're simply stepping too deep for answering the question here. You're right when you say that it is good to know how some things work on most common JVMs, but it is not of interest for questions like this one here.
The fact remains that this has nothing to do with the implementation of linked lists in Java. JVM internals were not part of the question.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.