Linked lists and vectors

Vector Representation {Vector data structure}

  • In this data structure suppose we have a list of 3 elements and if we need to add another in between 1st and the 2nd elements, So in vectors what happens is insertion by adding one element to the back and shift each and every element prior from the position we need to add. So it takes a lot of processing if we have like 1m elements.
  • In vectors the amount work is directly proportional to the number of elements in it.
  • So if we perform an insertion of deletion operation the amount of work grows linearly if we are using a vector.

                            So the issue is the amount of work is dependent.

For that we need to move to another data structure

Linked lists

  • In linked lists there are nodes to represent and element. Which contains all the information related to that element itself.
  • And there are links represented by and arrow. Which will refer the node. So each node is linked with the following node. There are no indexes to linked list. And the node linked together may place in anywhere in the memory. Key to all these is the links which connects the nodes as a pointer.
  • And the end of the node is referred to null (Ø) by the link / pointer to know that it’s the end of the list.
  • So suppose we have 3 nodes connected to each other and we need to add another node between 1st and 2nd, so the best part in linked list is we can simply point 1st one’s link to the new node and new nodes link to the 2nd Simple as that.
  • So in this the amount of work is independent from the number of elements. Which means if the number of elements are 10m or 20m the amount of work is not increased linearly.
  • There’s another type called double linked list where we can traverse from start and also from the end.
  • There are head and tail pointers to point the end and the beginning of a list.
  • Node can have data or objects from a data structure and has a pointer or a link.

The amount of work is independent from the number of elements.

Vectors                            Linked lists
Not so good in insertion and deletion operations. Efficient in insertion and deletion operations.

 

Dependent on the number of elements. Independent from the number of elements.
Selecting an element is faster and simpler, just have to find from the index and the value. Selecting is harder because there are no indexes, So should follow all the links to find the value.
Can use binary search. Cannot use binary search.

 

Linked list can be used anywhere we need fast insertions and deletions but not random access.

Advertisements