Linked List
Before the concept of linked list we should about arrays.
There are some limitations of arrays as a list.
Limitations of Arrays as Lists:
We have seen implementation of a list by Array. It is a property of an array that
its elements are placed consecutively in memory.
There may not be enough continuous memory locations to accommodate
entire Array. Even if there are more free memory locations scattered throughout
memory in the form of small free blocks.
Once we declare size of Array, it is not possible to increase or decrease it during
the execution of the program. If we need more elements to store in the Array,
there is need of changing its size in the declaration.
Usually, the number of items in any list is not known in advance in most cases.
If Array is used to implement a List, it could result in wastage of memory, if the
entire array space is not consumed.
In order to overcome these shortcomings of a Arrays as a List we need an
implementation of a List that
would not require static list size and
the memory is not reserved in the beginning. That is, the memory is
dynamically is assigned as the need arises.
Furthermore, that would not require continuous large free memory block
to store list and will be able to use scattered smaller free memory blocks.
Linked List implementation of a List is one such example.
, Linked List
Linked List is an implementation of a list using linked memory.
Linked List overcomes the limitations of Array based list implementation.
A linked list is a dynamic data structure that grows and shrinks without any
limitation on size (except total memory space)
Linked List is a linear collection of data elements.
The Linear order is not implemented by continuous memory locations but
through pointers linking data elements.
– It is not necessary that next element to a node will be placed in a location
adjacent to it. It may be anywhere in the memory. We have to keep track of next
element’s (or node’s) location.
Each data element in a Linked List is called a Node.
To create a linked list, at first, we define structure of individual elements or the
node. Each node is divided into two parts.
– Information Part
– Link Field or Next Pointer
The Information part can again consist of many data items.
The Next or Link pointer field holds the starting location of the next node.
Before the concept of linked list we should about arrays.
There are some limitations of arrays as a list.
Limitations of Arrays as Lists:
We have seen implementation of a list by Array. It is a property of an array that
its elements are placed consecutively in memory.
There may not be enough continuous memory locations to accommodate
entire Array. Even if there are more free memory locations scattered throughout
memory in the form of small free blocks.
Once we declare size of Array, it is not possible to increase or decrease it during
the execution of the program. If we need more elements to store in the Array,
there is need of changing its size in the declaration.
Usually, the number of items in any list is not known in advance in most cases.
If Array is used to implement a List, it could result in wastage of memory, if the
entire array space is not consumed.
In order to overcome these shortcomings of a Arrays as a List we need an
implementation of a List that
would not require static list size and
the memory is not reserved in the beginning. That is, the memory is
dynamically is assigned as the need arises.
Furthermore, that would not require continuous large free memory block
to store list and will be able to use scattered smaller free memory blocks.
Linked List implementation of a List is one such example.
, Linked List
Linked List is an implementation of a list using linked memory.
Linked List overcomes the limitations of Array based list implementation.
A linked list is a dynamic data structure that grows and shrinks without any
limitation on size (except total memory space)
Linked List is a linear collection of data elements.
The Linear order is not implemented by continuous memory locations but
through pointers linking data elements.
– It is not necessary that next element to a node will be placed in a location
adjacent to it. It may be anywhere in the memory. We have to keep track of next
element’s (or node’s) location.
Each data element in a Linked List is called a Node.
To create a linked list, at first, we define structure of individual elements or the
node. Each node is divided into two parts.
– Information Part
– Link Field or Next Pointer
The Information part can again consist of many data items.
The Next or Link pointer field holds the starting location of the next node.
