Data Structures
Stacks • Queues • Linked List • Doubly Linked List • Tree • Binary Search Tree
Data structure can be defined as the way to store and organize data, so that it can be used efficiently. Then, we use algorithms to manipulate the data in those structures.EFFICIENT DATA STRUCTURE = EFFICIENT ALGORITHMS.
1. STACKS
Stacks are linear data structure which follow a specific order in which the operations are being made. The order can be Last in First Out (LIFO) or First In Last Out (FILO).
 |
Figure 1.1
In figure 1.1, we begin with an empty stack. It shows a stack that can be implemented with an array and an integer. The integer, which is tos (top of stack) provides the array index of the top elements of the stack. So, the stack is empty when tos = -1. To push, tos is incremented and the new element if placed in the array position tos. Reaching the top element is trivial and we can perform the pop by decrementing tos. If the stack is full, then the push operation cannot be performed.
2. QUEUES
Queues are linear data structure which follows the First In First Out (FIFO) order.
Figure 2.1
The easiest implementation of the queue is to store the items in an array with the front item in the front position.
- back represents the position of the last item in the queue
- to enqueue we increment back & place the item.
dequeue is expensive. That is because by requiring the items to be placed at the start of the array, dequeue is forced to shift all the items one position after we remove the front item.
In figure 2.1, is shown that we can solve this issue when performing dequeue by incrementing front rather than shifting all the elements. Thus, when queue has 1 element, both front & back represent the array index of that element. For an empty queue, back must be initialized to front -1. This way we ensure that enqueue and dequeue are performed in constant time.
3. LINKED LISTS
Linked list is a linear data structure in which elements are linked using pointers. The property of a linked list is that changes to it can be made by using only constant number of data movements, which is an advantage over an array implementation.
The basic liked list type consists of a collection of dynamically and connected allocated nodes. In a singly linked list, each of the nodes consist of the data element and a link to the next node in the list. The last node in the list has a null next link.
Figure 3.1
In figure 3.1, the first node in the linked list is accessible by reference. By starting at the first item and following the chain of the next links, we can print/ search in the linked list. The two basic operations to be performed are insertion and deletion of the item x.
-INSERTION
Figure 3.2
To insert, we must define where the insertion is going to be done. If we have a reference to node in the list, then is would be easy to insert it immediately after that item.
1. Create new node(tmp)
2. copy in x
3. set tmp’s next link
4. set current’s next link
-DELETION
Figure 3.3
To perform deletion in linked lists, we should bypass the node. We need a reference to the node prior to the one we want to remove.
In the figure 3.3 it is shown that to remove item x from the linked list, we set current to be the node prior to x and then have current's next link bypass x.
The list . . a, x, b, . . now appears as . . a, b, . .
4. DOUBLY LINKED LISTS
A doubly linked list is a linked list that allows bidirectional traversal by storing two links per node.
The singly linked list doesn't efficiently support some important operations. Although it is very easy to go to front of the list, it is actually time consuming to go to the end.
Figure 4.1
Figure 4.2
Figure 4.1 shows the doubly linked list. Each of the nodes has two links (next & prev); searching and moving can be performed in both directions.
An empty doubly list contains a head and tail, connected as shown in figure 4.2.
Insertion and removing involves twice as many link changes as for single linked list. Different from single linked list, in doubly linked list we can remove the current node because we can obtain the previous node instantly. Insertion is done by getting new node and then changing pointers in the order that is indicated. (figure 4.3)
Figure 4.3
5. TREES
A tree can be defined as a set of nodes and directed edges that connect pairs of nodes. The rooted tree has the below properties:
- One node is determined as the root.
- Every node c (not including the root) is connected by an edge from one other node p. Node p is c'parent and c is one of p'children.
- A unique path traverses from the root of each node. The path length is the number of edges that should be followed.
A directed edge connects the parent to the child.
Figure 5.1
In figure 5.1 a tree is represented. The root of the tree is A and its children are: B, C, D and E. A is the root so it doesn't have any parent, while others B, C, D and E have A as parent. Nodes that have no children are called leafs. In this example, C, F, G, H, I and K are leaves. The length of the path from A to K is 3 edges.
A tree with N nodes must have N-1 edges; every node expect the parent has an incoming edge. The depth of a node in a tree is the length of the path from the root to the node. (Depth of the root is always 0). The height of a node in a tree is the length of the path from the node to the deepest leaf. In our example, height of E is 2.
Siblings are those nodes which have the same parent. (B, C, D and E are siblings)
First child/next sibling method (Figure 5.2)
- Keep the children of each node in a linked list of tree nodes, with each node keeping two links, one to its leftmost child (if it is not a leaf) and one to its right sibling (if it is not the rightmost sibling).
- Arrows that point downward are firstChild links, and arrows that point left to right are nextSibling links. We did not draw null links because there are too many of them.
Figure 5.2
Node B has both a link to a sibling (C) and a link to a leftmost child (F); some nodes have only one of these links and some have neither.
6. BINARY SEARCH TREES
Binary search trees have the following property: for every node X in the binary search tree, all smaller keyed nodes are in the left subtree and all larger keyed nodes are in the right subtree. All items in the tree can be ordered consistently. Duplicates are not allowed.
Figure 6.1
From the property, figure 6.1 is a binary search tree
Figure 6.2
From the property, figure 6.2 is not a binary search tree
Figure 6.3
Figure 6.3 shows the binary search tree before and after insertion of 6, respecting the BST property.
Removal operation is harder than insertion. That is because removing the selected node can disconnect other parts of the tree, so we should be careful when reattaching the tree and maintain the BST property.
Figure 6.4
In the figure 6.4 is shown the before and after deleting node 5.
If the node has two children, the deleted node is replaced by using the smallest item in the right subtree.
Some exercises I have on my github relating data structures can be found here.