Table of Contents

Description

Think of a linked list as a train, except the middle carts have their doors closed. You can only start at the front or back of the train. From there, to get to a specific cart, you have to walk through each cart in between until you get there.

• Composition
  • A linked list is a data structure composed of several isolated nodes.
  • Each node contains
    • A data element, e.g. an object, integer, or string.
    • Pointers, pointing to the next (and sometimes previous) nodes.
  • Lastly, there is are separate pointers to the head and tail (first and last) nodes.
• Linked Lists specialize in insertion and deletion.
  • You can insert/delete an element from the ends of a linked list very quickly, compared to other data structures.
• Properties
  • You can start at either end of the list, but not the middle of it.
  • An empty linked list has 1 node with value NULL. The head and tail pointers both point to it.
• Types of Linked Lists
  • Singly Linked List: Each node contains only a pointer to the next node. You can only go forwards through the list.
    • Pros
      • You save half the memory of a doubly linked list.
    • Cons
      • You can’t go backwards.
      • You can start at the tail node, but you’ll be stuck there.
      • Deleting the tail node will take longer
  • Doubly Linked List: Each node contains a pointer to both the next and previous nodes. You can go both forwards and backwards.
    • Pros
      • You can start at either end, and get to the other.
    • Cons
      • Will take up twice as much memory as a singly linked list. This is because every pointer takes up memory, and you need twice as many pointers to point to previous nodes.

Usage

• Use to model real-life objects with a similar structure.
  • Train
  • Tunnels (with sections).
• When to use doubly linked over singly linked
  • When you need to delete the last node of the list.
  • When you want to be able to start at either end, and get to the other end. Bidirectional movement.
• When to use over other data structures.
  • Use a Linked List when you want to quickly insert or remove an object from one end of the list, without having to traverse the entire list.
  • If you want to access an element in the middle of the list, don’t use a Linked List. Use an array instead.
  • If you want to search for a specific element that may be anywhere in the list, use a hash table instead.

Efficiency

• Search: This takes linear time because you have to start at one end of the list, then iterate through every node once until you find the one you’re looking for.
  • In the worst case, it’s at the other end of the list and you have to iterate through the entire list.
  • If the list becomes larger, it will take longer to iterate through the whole list.
• Insert:
  • Head/Tail: This takes constant time, because you have a pointer to the end nodes. All you have to do is create a new node and have the head pointer point to it.
    • Whether you do this on a large or small list, it makes no difference because you’re not iterating through it. Therefore, it’s constant time.
  • Middle: This requires you to start at one end, iterate through until you reach your target position, then add your node and change pointers. Since you’re iterating through each node once, it’s linear time.
• Remove
  • Head: This takes constant time, because you just have to go to the head, remove the node, then point the head pointer to the next node. No iteration required.
  • Tail: This takes longer for singly linked lists than doubly linked lists.
    • You have to go to the tail node, delete it, then set the tail pointer to the second to last node.
    • Singly: For a singly linked list, you can’t find the second to last node by going backwards. You have to iterate through the entire list from the head to find it. Therefore, it’s linear time.
    • Doubly: For a doubly linked list, you can find the second to last node by going backwards from the last node. Even for a large list, you only have to take one step backwards to find it. Therefore, constant time.
  • Middle: Whether you start at the head or tail, you have to iterate through most nodes once to get to your target node. That means it’s linear time.

Implementation

• How insertion works
  • Singly:
    1. Create a new pointer, that you’ll use to traverse the list.
    2. Start at the head node. Go forwards, one node at a time, until you get to the node before your insertion spot .
    3. Create a new node.
    4. Change 2 pointers
       1. Have the previous node (that your traversal pointer is on) point to the new node.
       2. Have your new node point to the next node.
  • Doubly
    1. Create a traversal pointer. Start at the head node.
    2. Traverse the list until you’re right before your insertion spot.
    3. Create a new node.
    4. Change 4 pointers
       1. Point the new node to (1) your current node and (2) the next node.
       2. Point your current node to the new node.
       3. Point the next node to the new node.