LINKED LISTS

In this blog post will study what is linked lists, arrays vs linked lists, advantages and disadvantages of linked lists, operations, types and applications of linked lists.

Definition

A linked list is a linear data structure used for storing collections of data. It consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
A linked list has the following properties:

  • Successive elements are connected by pointers.
  • The last element points to NULL.
  • Can grow or shrink in size during execution of a program.
  • It's a memory efficient DS.

Arrays vs Linked Lists

  • Elements are stored consecutively(contiguous memory block) in arrays whereas it is stored randomly in Linked lists.
  • Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible, can expand and contract its size.
  • In an array, memory is assigned during compile time while in a Linked list it is allocated during execution or runtime.
  • In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list.
  • Accessing an element in an array is fast(using index or subscript), while Linked list takes linear time, so it is quite a bit slower.

Advantages & Disadvantages

Advantages

The main advantage of linked lists is that they can be expanded in constant time. To create an array, we must allocate memory for a certain number of elements. To add more elements to the array when full, we must create a new array and copy the old array into the new array. This can take a lot of time.

Disadvantages

The main disadvantage of linked lists is access time to individual elements. Array is random-access, which means it takes O(1) to access any element in the array. Linked lists take O(n) for access to an element in the list in the worst case. Another advantage of arrays in access time is spacial locality in memory.

Sometimes linked lists are hard to manipulate. If the last item is deleted, the last but one must then have its pointer changed to hold a NULL reference. This requires that the list is traversed to find the last but one link, and its pointer set to a NULL reference.

Standard operations

  1. Traverse: Iterate through the nodes in the linked list starting from the head node.
  2. Insert: Add new node at front/rear or any specified posistion.
  3. Delete: Delete a node at front/rear or any specified posistion.
  4. Count: To find the no of nodes in linked list.
  5. Display: Traverse the linked list and display the data of each node.

Types

  1. Singly Linked Lists
  2. Doubly Linked Lists
  3. Circular Linked Lists

We will study each of this type in separate blog posts.

Applications

  • Can be used to implement stacks, queues and graphs.
  • Maintaining directry names.
  • Previous and next page in web browser.
  • Undo and redo in editors.
Similar posts: Singly Linked Lists | Circular Linked Lists | Doubly Linked Lists

That's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!

Copyright © NStF Blogs 2021