Linked lists non-contiguous memory [duplicate]

Question

This question already has answers here:

What is a contiguous memory block? (6 answers)

Closed 9 years ago.

I am having difficulty finding an answer to the following question from a past exam paper. I would appreciate an explanation.

Linked lists use non-contiguous memory, what does this mean?

Answer 1

Non-contiguous means that linked lists' elements are not necessarily in adjacent locations in memory. This is distinct from an array or an array list, which do use contiguous memory. For arrays and array lists, the consecutive elements are also in adjacent memory locations.

Answer 2

It means that each node of the list can be anywhere in memory. This is one thing which distinguishes lists from arrays, which are stored contiguously.

Answer 3

Linked list uses links, links points to next element in the list, these links don't have to be adjacent in memory. so each element in the linked list can be in any memory location and using the links we can traverse the list in a sequential manner. while arrays on the other side uses a contiguous memory block which means all elements are adjacent to each other.

Answer 4

Non-contiguous memory in this case is referring to the fact that the memory addresses assigned to the nodes which comprise the linked list, are not consecutive. Compare this to a traditional array, where each node occurs sequentially. In Languages with pointers (at least the C family) you can access the next index in an array by adding a number to the memory address which represents the index, instead of incrementing the index itself. Where the aforementioned number is the size in bytes of the data type contained in the array.

Back to linked lists and java...

In Java, you cannot access memory locations explicitly, but the underlying concept is still important for performance reasons. It is faster to access something in an array where the index is incremented by adding to a pointer, rather than accessing something in a linked list, where the next node needs to be jumped to. Therefore, access of an index in a linked list takes O(n) time, whereas an array is O(1) time.

I hope that made at least a little sense.

Answer 5

Linked lists present themselves as sequence of Nodes, which have member variables that point to the next (also could be previous) Node in the list. When you construct a linked list you usually construct it with the first Node, which will be the head. When a new element needs to be added to the linked list it first needs to be created. It gets created somewhere in the memory, could be the heap, could be stack. And the memory gets allocated by the OS, and it up to the OS which location of memory to give to us. Right after creating the new Node, we have to assign the "next" of the current node to that new node.

What is the data structure that is contiguous? An array.