8

I know how to implement linked list using array. For example we define a struct as follow:

struct Node{
    int data;
    int link;
}

"data" stores the info and "link" stores the index in the array of next node.

Can anybody tell me what is the advantage and disadvantage of implementing a linked list using array compared to "ordinary" linked list? Any suggestion will be appreciated.

Improve this question

4 Answers 4

Reset to default
10

If you back a linked list with an array, you'll end up with the disadvantages of both. Consequently, this is probably not a very good way to implement it.

Some immediate disadvantages:

  1. You'll have dead space in the array (entries which aren't currently used for items) taking up memory
  2. You'll have to keep track of the free entries - after a few insertions and deletions, these free entries could be anywhere.
  3. Using an array will impose an upper limit on the size of the linked list.

I suppose some advantages are:

  1. If you're on a 64 bit system, your "pointers" will take up less space (though the extra space required by free entries probably outweighs this advantage)
  2. You could serialise the array to disk and read it back in with an mmap() call easily. Though, you'd be better off using some sort of protocol buffer for portability.
  3. You could make some guarantees about elements in the array being close to each other in memory.
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

You would not necessarily need to track free entries. When you remove an item, simply move the last item to the vacated position and adjust indices. Then Count is all the tracking you need. I am not sure how this would impact performance compared to tracking, but it would still be O(1) complexity.
Cute, but I don't think you can do that without changing the data structure to support backlinks. Without backlinks, you'd have to search the whole list to find whatever was pointing to the last element in order to adjust the index.
I had not considered that, but you are right. Still, that's just an implementation detail--one more int in the Node. It adds a little overhead, but it would not change the time complexity. I have used a similar trick with binary heaps to get O(1) Contains.
2

Can anybody tell me what is the advantage and disadvantage of implementation of linked list using array compared to "ordinary" linked list?

linked lists have the following complexity:

  • cons x xs : O(1)
  • append n m : O(n)
  • index i xs : O(n)

if your representation uses a strict, contiguous array, you will have different complexity:

  • cons will require copying the old array: O(n)
  • append will require copying both arrays into a new contiguous space: O(n + m)
  • index can be implemented as array access: O(1)

That is, a linked list API implemented in terms of arrays will behave like an array.

You can mitigate this somewhat by using a linked list or tree of strict arrays, leading to ropes or finger trees or lazy sequences.

Improve this answer

1 Comment

It seems that insertion is O(1) still, and not O(n), so it isn't exactly like an array.
0

stack in implement two way. first in using array and second is using linked list.

some disadvatages in using array then most of programmer use linked list in stack implement.

first is stack using linked list first not declare stack size and not limited data store in stack. second is linked list in pointer essay to declare and using it.

only one pointer use in linked list. its called top pointer.

stack is lifo method use. but some disadvantages in linked list program implemention.

Most of programmer use stack implemention using liked list.

Improve this answer

Comments

0

Using Array implementation, you can have sequential & faster access to nodes of list, on the other hand, If you implement Linked list using pointers, you can have random access to nodes. Array implementation is helpful when you are dealing with fixed no. Of elements because resizing an array is expensive as far as performance is concerned because if you are required to insert/delete nodes from middle of the list it you have to shift every node afterwise. Contrary to this, You should use pointer implemention when you don't know no. of nodes you would want, as such a list can grow/shrink efficiently & you don't need to shift any nodes, it can be done by simply dereferencing & referencing pointers.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.