Data Structures

Linked Lists

Definition: A linear collection of nodes in which each node links to the next node.

Singly Linked List

Each node has a single pointer to the next node.

When to Use:

• Need constant time insertion or deletion
  • Only at head (front of list)
  • Inserting elements is easier in singly linked list that in doubly linked list
• Unknown number of elements
• No need for random access
• Need linked list and memory is a concern
  • Requires less memory than doubly linked list

Time Complexity:

	Average	Worst
Access	θ(n)	O(n)
Search	θ(n)	O(n)
Insertion	θ(1)	O(1)
Deletion	θ(1)	O(1)

Doubly Linked List

Each node has two pointers, one to the previous node and one to the next node.

When to Use:

• Need constant time insertion or deletion
  • Only at head or tail (front or back of list)
  • Doubly linked list deletion is faster that singly linked list deletion, except when deleting the head
• Unknown number of elements
• No need for random access

Time Complexity:

	Average	Worst
Access	θ(n)	O(n)
Search	θ(n)	O(n)
Insertion	θ(1)	O(1)
Deletion	θ(1)	O(1)

*** # Stacks **Definition:** An abstract data type that supports a last in, first out (LIFO) policy. A push method is used to add an element onto the stack and a pop method is used to remove the most recent element of the stack.

When to Use:

• List reversal
• Parsing
• Expression conversion and evaluation
  • Balancing delimiters
• Tower of Hanoi

Time Complexity:

	Average	Worst
Access	θ(n)	O(n)
Search	θ(n)	O(n)
Insertion	θ(1)	O(1)
Deletion	θ(1)	O(1)

*** # Queues **Definition:** Elements within this abstract data type are ordered by a specified principle. An enqueue method adds an element to the back of the queue, while a dequeue method removes an element from the front of the queue.

FIFO

The traditional queue policy is first in, first out (FIFO), just like a line for a service. Elements which are added to the queue more recently are accessible sooner than elements added to the queue later on.

When to Use:

• Need to maintain order
• Packet transmission
• Providing a service in which clients are all valued equally

Time Complexity:

	Average	Worst
Access	θ(n)	O(n)
Search	θ(n)	O(n)
Insertion	θ(1)	O(1)
Deletion	θ(1)	O(1)

Deque

Elements can be inserted and removed from both the front and back of this type of queue.

When to Use:

• Need access to old and new elements
• Providing a service that is likely to require clients to return
  • A fast food cashier serves a customer their order but forgets to include ketchup packets
    • The customer is allowed to cut the line to get ketchup packets.

Time Complexity:

	Average	Worst
Access	θ(n)	O(n)
Search	θ(n)	O(n)
Insertion	θ(1)	O(1)
Deletion	θ(1)	O(1)