linear_data_structures.md

Linear data structures

The data structures described here are fundamental to many algorithms. They are used for storing an ordered collection of elements. Each of the structures has its own benefits and we'll learn how to take advantage of them in order to speed up our algorithms.

Array

Arrays are essential to many algorithms. They are very close to the memory representation in a machine and provide efficiant (O(1) time) operations for working with elements at a random position.

Arrays are key ingrediants in other more complex data structures.

Vector

Vectors are modification of arrays that allow unlimited number of elements to be added to the collection while keeping the performance of random access operations similar to array's (approximately O(1) time).

• C++: std::vector
• Java: java.util.ArrayList
• Python: list

List

List is a data structure that allows us to store unlimited number of elements without copying them over when expanding. In order to achieve this it does not store the elements in an Array. Instead, every element is an object that holds both the value (int, string, float, etc...) and a pointer to the next element in the list. This way every element of the list could be accessed starting from the first element (we call this head of the list) and following the links.

List sacrifices the performance of accessing elements at random position (this operation runs in O(n) time) so that adding, removing and retrieving elements from the end of the list is fast (runs in O(1) time).

Linked list - List with link in one direction.

Doubly linked list - List with links in both directions.

• C++: std::list
• Java: java.util.LinkedList
• Python: collections.deque

Queue

Queue is an abstract data type. This means that it does not define a specific implementation. It just provides an interface for the supported operations.

The interface of a Queue data type is:

Queue {

  // Adds value to the end of the Queue.
  // Complexity: O(1)
  push(value)

  // Returns value from the front of the Queue and removes it.
  // Complexity: O(1)
  pop()

  // Returns value from the front of the Queue without removing it.
  // Complexity: O(1)
  peek()

  // Returns the number of elements in the Queue.
  // Complexity: O(1)
  size()
}

It could be implemented with both Vector and List.

• C++: std::queue
• Java: java.util.Queue
• Python: collections.deque

Stack

Stack is an abstract data type. This means that it does not define a specific implementation. It just provides an interface for the supported operations.

The interface of a Stack data type is:

Stack {

  // Adds value to the end of the Stack.
  // Complexity: O(1)
  push(value)

  // Returns value from the end of the Stack and removes it.
  // Complexity: O(1)
  pop()

  // Returns value from the end of the Stack without removing it.
  // Complexity: O(1)
  peek()

  // Returns the number of elements in the Stack.
  // Complexity: O(1)
  size()
}

It could be implemented with both Vector and List.

• C++: std::stack
• Java: java.util.Stack
• Python: collections.deque