Linked list

About Linked List

• Linked lists are one of the most commonly used data structures after arrays.
• They solve many problems faced by arrays.
• They are used to build more complex data structures.

What is a Linked list

• Linked list is a data structure that is used to store data in sequence.
• Unlike the arrays where the size is fixed and with a fixed number of elements, the Linked list can grow and shrink as needed.
• So they are like a sequence of nodes. The Node has 2 parts one is the info field and the other is called the address field. A node has an address field using which we point to the next node.
• So in the list, we say each node point to or references the next node in the list, thus this structure is called linked list.
• Now here in the list, we call the first node the head and the last node as the tail.

Time Complexity of operations

• Lookup Operation
  • Lookup by value --> Run time complexity is O(n) - This is because, in order to find an element, we need to traverse a list and find the element we are looking for. In the worst-case scenario, it's at the end of the list
  • Lookup by index --> Run time complexity is being O(n) - This is because, unlike the arrays where the elements are next to each other, the nodes of a list might be all over the memory distributed and connected to each other by the address fields in the chain. Thus in the worst-case scenario, it's O(n).
• Insertion Operation
  • Insertion at the end of linked list -------> Run time complexity is -----> O(1)
  • Insertion at the begining of linked list --> Run time complexity is -----> O(1)
  • Insertion at the middle of linked list ----> Run time complexity is -----> O(n)
• Deletion Operation
  • Deletion at the end of linked list -------> Run time complexity is -----> O(n)
  • Deletion at the begining of linked list --> Run time complexity is -----> O(1)
  • Deletion at the middle of linked list ----> Run time complexity is -----> O(n)