Linked List

One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions and deletions. In this chapter we consider another data structure called Linked Lists that addresses some of the limitations of arrays.

A linked list is a linear data structure where each element is a separate object.
Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. 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.
Linked Lists are used to create trees and graphs.

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.
 Types of Linked Lists

There are 3 different implementations of Linked List available, they are:
Let's know more about them and how they are different from each other. 

Singly Linked List

Singly linked lists contain nodes which have a data part as well as an address part i.e. next, which points to the next node in the sequence of nodes.
The operations we can perform on singly linked lists are insertiondeletion and traversal.

Doubly Linked List

In a doubly linked list, each node contains a data part and two addresses, one for the previous node and one for the next node.

Circular Linked List

In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.

Difference between Array and Linked List

Both Linked List and Array are used to store linear data of similar type, but an array consumes contiguous memory locations allocated at compile time, i.e. at the time of declaration of array, while for a linked list, memory is assigned as and when data is added to it, which means at runtime.
This is the basic and the most important difference between a linked list and an array. In the section below, we will discuss this in details along with highlighting other differences.

Linked List vs. Array

Array is a datatype which is widely implemented as a default type, in almost all the modern programming languages, and is used to store data of similar type.
But there are many usecases, like the one where we don't know the quantity of data to be stored, for which advanced data structures are required, and one such data structure is linked list.
Let's understand how array is different from 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[6] 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, upto 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 formaing a link between the two nodes/elements.
In array, Insertion and Deletion operation takes more time, as the memory locations are consecutive and fixed.
In case of linked list, a new element is stored at the first free and available memory location, with only a single overhead step of storing the address of memory location in the previous node of linked list.
Insertion and Deletion operations are fast in linked list.
Memory is allocated as soon as the array is declared, at compile time. It's also known as Static Memory Allocation.Memory is allocated at runtime, as and when a new node is added. It's also known as Dynamic Memory Allocation.
In array, each element is independent and can be accessed using it's index value.In case of a linked list, each node/element points to the next, previous, or maybe both nodes.
Array can single dimensionaltwo dimensional or multidimensionalLinked list can be Linear(Singly)Doubly or Circularlinked list.
Size of the array must be specified at time of array decalaration.Size of a Linked list is variable. It grows at runtime, as more nodes are added to it.
Array gets memory allocated in the Stack section.Whereas, linked list gets memory allocated in Heapsection.
Below we have a pictorial representation showing how consecutive memory locations are allocated for array, while in case of linked list random memory locations are assigned to nodes, but each node is connected to its next node using pointer.


    No comments: