- A Linked List is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence.
- Singly-linked list: linked list in which each node points to the next node and the last node points to null
- Doubly-linked list: linked list in which each node has two pointers, p and n, such that p points to the previous node and n points to the next node; the last node's n pointer points to null
- Circular-linked list: linked list in which each node points to the next node and the last node points back to the first node
- Time Complexity:
- Access:
O(n) - Search:
O(n) - Insert:
O(1) - Remove:
O(1)
- Access:
- A Stack is a collection of elements, with two principle operations: push, which adds to the collection, and pop, which removes the most recently added element
- Last in, first out data structure (LIFO): the most recently added object is the first to be removed
- Time Complexity:
- Access:
O(n) - Search:
O(n) - Insert:
O(1) - Remove:
O(1)
- Access:
- A Queue is a collection of elements, supporting two principle operations: enqueue, which inserts an element into the queue, and dequeue, which removes an element from the queue
- First in, first out data structure (FIFO): the oldest added object is the first to be removed
- Time Complexity:
- Access:
O(n) - Search:
O(n) - Insert:
O(1) - Remove:
O(1)
- Access:
- A Tree is an undirected, connected, acyclic graph
- A Binary Tree is a tree data structure in which each node has at most two children, which are referred to as the left child and right child
- Full Tree: a tree in which every node has either 0 or 2 children
- Perfect Binary Tree: a binary tree in which all interior nodes have two children and all leave have the same depth
- Complete Tree: a binary tree in which every level except possibly the last is full and all nodes in the last level are as far left as possible
- A binary search tree, sometimes called BST, is a type of binary tree which maintains the property that the value in each node must be greater than or equal to any value stored in the left sub-tree, and less than or equal to any value stored in the right sub-tree
- Time Complexity:
- Access:
O(log(n)) - Search:
O(log(n)) - Insert:
O(log(n)) - Remove:
O(log(n))
- Access:
- A trie, sometimes called a radix or prefix tree, is a kind of search tree that is used to store a dynamic set or associative array where the keys are usually Strings. No node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the String associated with that node, and the root is associated with the empty String.