CODEWITHSUNDEEP
data-structureslinked-list
yvetterowe
yvetterowe

Reputation: 1279

implement linked list using array - advantages & disadvantages

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.

Upvotes: 8

Views: 35283

Answers (4)

Shashikant Mitkari
Shashikant Mitkari

Reputation: 307

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.

Upvotes: 0

Solomon Bindavid
Solomon Bindavid

Reputation: 83

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.

Upvotes: 0

Don Stewart
Don Stewart

Reputation: 138007

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.

Upvotes: 2

Timothy Jones
Timothy Jones

Reputation: 22165

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.

Upvotes: 10

Related Questions