Ø
Linked List –
·
A linked list is a sequence of data structure which are connected
together via links.
·
A linked list is a linear data structure.
·
Linked list is a data structure which can be used to implement
other data structure such as stack, queue and their variations.
·
Linked List is a very commonly used linear data structure which
consists of group of nodes in a sequence.
·
Each node contain two part –
i.
Data
ii.
Address
·
The data part is used to store element or data.
·
The address part is used to store the address of next node in a
sequence..
·
Linked Lists are used to create trees and graphs.
·
A linked list is a dynamic data structure.
·
The linked list is implement using the following code –
Struct node
{
Int data;
Struct node *next;
};
·
Any application which has to deal with an unknown number of
objects will need to use a linked list.
·
One disadvantage of a linked list against an array is that it does
not allow direct access to the individual elements.
·
If you want to access a
particular item then you have to start at the head and follow the references
until you get to that item.
·
Another disadvantage is that a linked list uses more memory
compare with an array - we extra 4 bytes (on 32-bit CPU) to store a reference
to the next node.
Advantages of Linked
Lists -
- They are a dynamic in nature which allocates the memory when required.
- Insertion and deletion operations can be easily implemented.
- Stacks and queues can be easily executed.
- Linked List reduces the access time.
Disadvantages of Linked Lists -
- The memory is wasted as pointers require extra memory for storage.
- No element can be accessed randomly; it has to access each node sequentially.
- Reverse Traversing is difficult in linked list.
Applications of Linked Lists -
- Linked lists are used to implement stacks, queues, graphs, etc.
- Linked lists let you insert elements at the beginning and end of the list.
- In Linked Lists we don't need to know the size in advance.
Linked List vs. Array -
|
ARRAY
|
LINKED LIST
|
|
Array is a collection of elements of similar data
type.
|
Linked List is an ordered collection of elements
of same type, which are connected to each other using pointers.
|
|
Array supports Random
Access, which means elements, can be accessed directly using their index,
like arr [0] for 1st element, arr [0] for 7th element etc.
Hence, accessing elements in an
array is fast with a constant time complexity of o(1)
|
Linked List supports Sequential
Access, which means to access any element/node in a linked list, we have
to sequentially traverse the complete linked list, up to that element.
To access nth element
of a linked list, time complexity is o(n).
|
|
In an array, elements are
stored in contiguous memory location or consecutive manner
in the memory.
|
In a linked list, new elements
can be stored anywhere in the memory.
Address of the memory location
allocated to the new element is stored in the previous node of linked list,
hence forming a link between the two nodes/elements.
|