Linked List

#DataStructure#Computer-Science#CS251

• Linked Lists are a dynamic linear data structure
• There are a few kinds of linked lists
  • Singly Linked List: each node in the list points to the next element in the list
  • Doubly Linked List: each node in the list points to the next element and previous element in the list
  • Circularly linked list: the last element in the list points to the first (and in a doubly circular linked list, the first element will point to the last element)
• Accessing data in a linked list is $\in O(n)$
  • This is because you will have to traverse through the list to get to the item you are accessing
• Inserting an element into the list
  • Inserting at the front of the list $\in O(1)$
  • Inserting at the back of the list:
    • If you have a pointer to the tail of the list: $\in O(1)$
    • Otherwise, $\in O(n)$
  • Inserting into the middle of the list: $\in O(n)$
• Deleting an element from the list
  • Singly linked list $\in O(n)$ since you have to always loop from the front to find the previous node to set the next pointer of
  • Doubly linked list $\in O(1)$ since you can just look at the node that’s being deleted to find the previous/next nodes and set their pointers