Introduction to LinkedList data structure 

A linked list is a data structure that consists of a chain of elements called nodes. Each node has two parts: a value and a pointer. The value is the data stored in the node, and the pointer is a reference to the next node in the list. The first node in the list is called the head, and the last node is called the tail. The head’s pointer points to the next node in the list, the next node’s pointer points to the node after that, and so on. The tail node’s pointer points to None, signifying the end of the list.

Let’s create a singly linked list that stores the names of the days of the week. We would first create the head node, containing the value “Monday” and a pointer to the next node. Next, we would make the second node have the value “Tuesday” and a pointer to the next node. This process would be repeated for the remaining days of the week, creating a new node for each day with a value of the day and a pointer to the next node. The last node, Sunday, will have a pointer pointing to None.

In this example, the head node would be the Monday node, which contains the value “Monday” and a pointer to the next node, the “Tuesday” node. The “Tuesday” node contains the value “Tuesday” and a pointer to the next node, which is the “Wednesday” node, and so on. The last node is the “Sunday” node which contains the value “Sunday” and a pointer that points to None.

Implement link list in Python

class Node:
  def __init__(self, data):
      self.data = data
      self.next = None

class LinkedList:
  def __init__(self):
      self.head = None

  def add_node(self, data):
      new_node = Node(data)A
      new_node.next = self.head
      self.head = new_node

  def traverse_list(self):
      current = self.head
      while current:
          print(current.data)
          current = current.next

weekdays = LinkedList()
weekdays.add_node("Monday")
weekdays.add_node("Tuesday")
weekdays.add_node("Wednesday")
weekdays.add_node("Thursday")
weekdays.add_node("Friday")
weekdays.add_node("Saturday")
weekdays.add_node("Sunday")
weekdays.traverse_list()

The following will be the output of the above code:

Saturday
Friday
Thursday
Wednesday
Tuesday
Monday

In this example, we have defined two classes: Node and LinkedList. The Node class has two attributes: data and next. The data attribute stores the actual data of the node, in this case, the day of the week. The next attribute is a reference to the next node in the list.

The LinkedList class has a head attribute that stores a reference to the first node of the list. The class has two methods: add_node and traverse_list. The add_node method creates a new node with the given data and makes it the new head of the list. The traverse_list method starts at the head of the list and follows the pointers to the next node, printing the data of each node until it reaches the tail node (node that points to None).

In the last line of the code, we create an instance of the LinkedList class called “weekdays” and add the days of the week to the list using the add_node method. Finally, we traverse the list using the traverse_list method, which prints the day

Use Cases of the linked list

• Dynamic memory allocation: Linked lists do not have a fixed size and can grow or shrink as needed, making them useful for dynamic memory allocation. This is useful when the number of elements in a data structure needs to change frequently.
• Implementing other data structures: Linked lists are often used to implement other data structures such as stacks, queues, and associative arrays.
• Efficient insertion and deletion: Inserting or deleting an element in a linked list is an efficient operation as it only requires updating the pointers of the adjacent elements, rather than moving a large block of memory like in arrays.
• Sorting: Linked lists can sort elements quickly using sorting algorithms such as merge sort, as linked lists allow for efficient element insertion and deletion.
• Caching: Linked lists can be used to implement caching, where the most recently accessed elements are moved to the front of the list to allow faster access.
• Circular Lists: Linked lists can be used to implement circular lists, where the last element points to the first element and vice-versa. This can be used when the list needs to be continuously cycled through.

Limitations of Linked list

• Random access: Linked lists are not designed for random access, meaning it’s inefficient to access an element at a specific position in the list, as each element needs to be traversed one by one to reach the desired element.
• Space overhead: Each element in a linked list requires additional memory to store the pointer to the next element, which can be a significant space overhead for large lists.
• Cache performance: linked lists have poor cache performance compared to arrays, as the memory is not contiguous, so it takes longer to access elements.
• Extra space complexity: Linked lists have extra space complexity as it needs to store extra information (pointers) in addition to the data.
• Large size: linked lists can’t handle large amounts of data as it can cause a stack overflow error.