Data Structures — Part 8 (Heap-based Priority Queue)

Heap-based priority queue consists of the following:

• heap: A complete binary tree T whose elements are stored at internal nodes and have keys satisfying the heap-order property. For each internal node v of T, we denote the key of the element stored at v as k(v).
• last: A reference to the last node of T
• comp: A comparator that defines the total order relation among the keys. Without loss of generality, we assume that comp maintains the minimum element at the root. If we wish the maximum element to be at the root, we can redefine our comparison rule accordingly.

Heap-based priority queue storing integer keys and text elements

A heap T storing n keys has height h=[log(n+1)]

I already mentioned in previous post that when inserting item in heap, that item will be inserted into lowest-right position in the tree. In order to store a new key-element pair (k, e) into T, we need to add a new internal node to T, and since we need to add new node to lowest-right position in T, we must identify the correct external node z where we will store new node. Node z is called insertion position.

When adding node to a heap, we might violate heap-order property, and then we need to move new node ‘up the heap’ in order to fix this issue. The upward movement by means of swaps is conventionally called up-heap bubbling.

So, let’s consider adding new value to the heap above. Let’s add value T and assign it key (priority) 2… that means that we are adding node (2, T) to the heap. Insert position is left child of node (20, B):

(2, T) node is added to the heap:

New node (2, T) does not satisfy heap-order property (parent node (20, B) does not have smaller key than the new node: 20 > 2)… So we need to swap new node with it’s parent node:

This is how heap looks after swapping:

New node (2, T) still violates heap-order property (parent node (6, Z) does not have smaller key than the new, child node: 6 > 2)… So we need to swap new node with it’s parent node:

Here is how heap looks after the swap:

 

New node (2, T) still violates heap-order property (parent node (4, C) does not have smaller key than the new, child node: 4 > 2)… So we need to swap new node with it’s parent node:

 

This is tree after swapping:

Now the tree is real heap and is not violating heap properties.

Here is described worst-case scenario where new node will "bubble-up" all the way to the root of the heap. In worst case scenario up-heap bubbling will take O(log n) time, since heap is a complete tree.

I already mentioned in previous post that when removing item from heap (using removeMin method), removed item will be the root node. If root node is not the only node in the heap, then it can’t be simply removed. What we need to do is provide another root node for the heap. We will choose last node in the heap and use it as a node. This might violate heap-order property, and in that case we need to use down-heap bubbling.

Algorithm for down-heap bubbling works:

• If both children of new root r are external nodes, than we don’t need to do anything.
• If left child of r is internal and the right node is external, let s be the left child of r.
• If both child nodes are internal, let s be a child of r with the smallest key.

Let’s explain this through example… Let’s start with a heap:

Now we remove root node and place last node as a new root node:

This is how the tree looks like:

Since now heap-order property is violated, we need to do down-heap bubbling. We will replace node (13, W) with child node with smaller key: (5, A) node, since key 5 is less than key 6.

This is how tree looks like after swapping:

Heap-order property is violated again, we need to do down-heap bubbling. We will replace violating parent node (13, W) with child node with smaller key: (9, F) node, since key 9 is less than key 15.

This is how tree looks like after swapping:

Heap-order property is violated again, we need to do down-heap bubbling. We will replace violating parent node (13, W) with child node with smaller key: (12, H) node, since key 12 is less than key 14.

This is how tree looks like after swapping:

       

Now the tree is real heap and is not violating heap properties.

Here is described worst-case scenario where new node will "bubble-down" all the way to the last level of the heap. In worst case scenario down-heap bubbling will take O(log n) time, since heap is a complete tree.

Thinking of performance: each of the methods on heap-based priority queue can be performed in O(1) or in O(log n) time, where n is the number of elements at the time the method is executed. As a conclusion, its OK to say that heap data structure is very efficient realization of the priority queue, independent of whether the heap is implemented with a linked structure or a sequence. The heap implementation achieves fast running times for both insertion and removal, unlike the sequence-based priority queue implementations.

Data Structures — Part 7 (Priority Queue and Heap)

Priority queue is a container of elements, each having an associated key that is provided at the time the element is inserted. The name "priority queue" comes from the fact that keys determine the "priority" used to pick elements to be removed.

The two fundamental methods of a priority queue are:

• insertItem(k,e) – insert an element e with key k into priority queue
• removeMin() – return and remove from priority queue an element with the smallest key

Elements are added/removed based on their keys, not based on their values.

Priority Queue Sort

The algorithm for sorting collection C with a priority queue Q is quite simple and consists of the phases:

• Put elements of C into an initially empty priority queue P by means of a series of n insertItem operations, one for each element
• Extract elements from P in non-decreasing order by means of a series of n removeMin operations, putting them back into C in order

Algorithm PQ-Sort (C, P):   //assumes that C is a sequence (e.g. vector)

Input: n-element sequence C and priority queue P that compares keys, which are elements of C

Output: Sorted sequence C

while C is not empty do

e = C.removeFirst();  //remove element e from C

P.insertItem(e, e);   //the key is the element itself

while P is not empty do

e = P.removeMin();   //remove a smallest element from P

C.insertLast(e);   //add the element at the end of C

When someone says "priority queue", that only means that there is a key associated with the value, and it does not describe how those elements (values) are ‘organized’ within data structure. Priority queue requires some other data structure in order to be implemented.

A realization of a priority queue that is efficient for both insertions and removals uses a data structure called a heap. This data structure allows us to perform both insertions and removals in logarithmic time. Heap stores elements and keys in a binary tree.

A heap is a binary tree T that stores a collection of keys at its internal nodes and that satisfies two additional properties:

• A relational property: heap-order property – in heap T, for every node v other than the root, the key stored at v is greater than or equal to the key stored at v’s parent.
• A structural property: complete binary tree – a binary tree T with height h is complete if the levels 0, 1, 2, … , h-1 have the maximum number of nodes possible, and in level h-1 all the internal nodes are to the left of the external nodes.

Note that heap does not always contain value and key – if we decide to do so, we can use value as keys (as in the tree below).

Last node of heap T is the right-most, deepest internal node of T.

Heap storing 13 integer keys. The last node is node with key 8; all external nodes are empty.

Looking at the heap, we identify that heap is a binary balanced tree. Every new node is added to the lowest-right available position. When removing node, we remove root. After we add node, tree might need to be restructured; and after removing node, tree must be restructured.

More about insertion/removal and restructuring tree will be in next post.

Next: Data Structures — Part 8 (Heap-based Priority Queue)

Graphs — Part 1 (Introduction)

Connectivity information can be defined by all kinds of relationships that exist between pairs of objects; Graphs can be used to represent algorithms and efficiently deal with such relationships. That is, a graph is a set of objects, called nodes (vertices), together with a collection of pairwise connections (arcs) between them.

Graphs have applications in a host of different domains, including mapping (in GIS), transportation (road/flight networks), electrical engineering (circuits), computer networking… whenever there is some relationship between two (or more) objects – you can use graphs.

Viewed abstractly, a graph is a set of vertices (nodes) and a collection of pairs of nodes, called edges (arcs).

Edges can be directed or undirected. Graph containing only undirected edges is called undirected graph. Graph containing only directed edges is called directed graph or digraph. Graph containing both directed and undirected edges is called mixed graph. 

Graphs can be used to help solve problems. What I found especially useful when using graphs is possibility to visually present the problem. Use of graphs for solving problems is usually shown with problem called "bridges of Konigsberg". That was the problem I heard of during my undergraduate studies, and that is what I’m going to use here to show you how useful graphs can be…

Bridges of Konigsberg problem: There are seven bridges like on the image below…

Problem is: can you cross every bridge exactly once? Prove it.

If answer is yes, then it’s easy to prove it – you just need to go over every bridge once… But if answer is no, how can you prove it? This is where graphs come in… First, let’s mark every ‘land’ with a letter:

So now, we can see ‘land’ as nodes and bridges as edges:

So now, we have problem shown with a graph. Graph above is undirected. How do we use this graph in order to solve/prove the problem?

We need to prove that graph is (or is not) traversable. Traversable graph is a graph which has path for traversing each edge exactly once.

Looking at the graph – how can you determine if is traversable? Now… this is where Euler’s theory comes: Graph is traversable if only two or zero nodes have odd degree.

Nodes with odd degree will be ‘dead end’ if they are not starting and/or ending node.

Looking at graph above, we have nodes:

• A has level 3 (3 edges are entering/leaving node A);
• B has level 3 (3 edges are entering/leaving node B);
• C has level 5 (5 edges are entering/leaving node C);
• D has level 3 (3 edges are entering/leaving node D).

That is, 4 nodes have odd levels – which means that graph is not traversable… and the answer to the starting question is: No, you can’t cross every bridge exactly once.

That is one problem solved with use of graph… or more accurately: with graph we proved that there is no solution to the problem.

Below is sample directed graph which represents airports and flights to/from them… we will use it to explain some other terms related to graphs.

We say that SEA and ORD are adjecent – they are connected with edge DL 335.

ORD has out-degree=2 (edges ‘leaving’ the node); and in-degree=3 (edges ‘entering’ the node).

Path is a sequence of alternating edges and nodes which starts at node and ends at node, such that each edge is incident to its predecessor and successor node. E.g. path between SEA and LAX can be represented with any of the paths:

• AA 450;
• AA 43, DL 10;
• DL 335, NW 35, DL 10;
• DL 335, AA 14, NW 150, NW 35, DL 10;
• DL 335, AA 14, DL 25, AA 63.

Cycle is a path with the same start and end nodes. We say that path is simple if each node in the path is distinct, and we say that a cycle is simple if each node in the cycle is distinct, except for the first and last one. Graph is connected if for any two nodes, there is a path between them.

A forest is a graph without cycles. A tree is a connected forest, that is, a connected graph without cycles.

There are more terms associated with graphs, but we will identify and define them when needed.

Graphs — Part 2 (Data structures for graphs)… coming soon

Data Structures — Part 6 (Balanced trees)

As we already discussed, tree data structure can give great performance for find(x), insert(x), remove(x) operations: O(logn) – but this will be true if we have good balance between tree nodes, usually tree will not be very well balanced (remember tree which looks like array discussed in post Part 4 (Trees))… To make sure that we have best possible performance, we need to balance our tree.

Tree is balanced if for every node his children’s level is differing by at most 1 level. Let me explain this through example… Here is one balanced tree with levels marked next to the nodes:

Note that ‘null’ nodes are not shown: each node has pointers to left and right child, and if child node does not exist, parent node is pointing to null node, e.g. Node with value 17 has leftChild = null, rightChild = 31.

Null nodes are always on level 0.

Determining level of node goes bottom-up. Null nodes are on level 0 (not shown here), parent nodes of null nodes are level 1, etc. If node v has two child nodes, one with level 2 and one with level 4, node v will be on level 5 – we always take bigger value.

This tree (above) is balanced because all child nodes have level different for 1 or less. e.g:

• For root node 45, child nodes have levels 2 (17) and 3 (75) – difference is 1
• For node 75, child nodes have levels 2 (51) and 1 (78) – difference is 1
• For node 17, child nodes have levels 0 (null node) and 1 (31) – difference is 1
• For node 51, child nodes have levels 1 (47) and 1 (60) – difference is 0
• etc.

Tree can become unbalanced after insert(x) and/or remove(x) operations. So, what we do when tree becomes unbalanced? There are four distinct scenarios how to balance tree described above. Note that T0, T1, T2, T3 are child nodes – they can be null nodes, or nodes with value… they can be even subtrees.

We restore the balance of the nodes in the binary tree by simple "search-and-repair" strategy. Let z be the first node we encounter in going up toward the root such that z is unbalanced. y is the child of z with higher height. x is child of y with higher height. Trinode restructure temporarily renames nodes x, y, z as a, b, c so that a precedes b and b precedes c in an inorder traversal of tree. There are four possible ways of mapping x, y, z to a, b, c – which are unified into one case by relabeling (see below):

Case 1: single rotation

 

Case 2: single rotation

 

Case 3: double rotation

 

Case 4: double rotation

 

Algorithm restructure(x):

Input: Node x of a binary tree T that has parent y and grandparent z.

Output: Tree T after trinode restructuring involving nodes x, y, z

1. Let (a, b, c) left-to-right (inorder) listing of the nodes x, y, z and let (T0, T1, T2, T3) be left-to-right listing of the four subtrees of x, y and z not rooted and x, y or z.
2. Replace the subtree rooted at z with new subtree rooted at b.
3. Let a be the left child of b and let T0 and T1 be left and right subtrees of a, respectively
4. Let c be the right child of b and let T2 and T3 be the left and right subtrees of c, respectively

Let me go through this with example… Let’s take balanced tree:

and add node which will make this tree unbalanced: e.g. add node with value 57:

Going bottom-up and checking levels of each node, you can notice that node with value 75 has unbalanced child nodes (level 3 (51) and level 1 (78) – difference is more than 1 in levels). Since 75 is first unbalanced node going from bottom to the root of the tree, we mark node 75 as node z. 51 is child of 75 with higher height, and we mark it as y. 60 is child of 51 with higher height, and we mark it as x.

Not shown on image above:

• T0 = Left child of y (51): 47 (with it’s child nodes)
• T1 = Left child of x (60): 57 (with it’s child nodes)
• T2 = right child of x (60): null node
• T3 = right child of z (75): 78 (with it’s child nodes)

This is the fourth case described above. When we apply algorithm restructure(x), we get as result balanced tree:

   

Not shown on image above:

• T0 = Left child of y (51): 47 (with it’s child nodes)
• T1 = Right child of y (51): 57 (with it’s child nodes)
• T2 = Left child of z (60): null node
• T3 = Right child of z (75): 78 (with it’s child nodes)

Removing node from a balanced tree

Removal of node from a balanced tree is same as removing node from binary tree (unbalanced one)… this was discussed in post Part 4 (Trees). But what happens when removing node causes tree to be unbalanced? Then you need to appy algorithm restructure(x) to make it balanced. Example:

Let’s take balanced tree from example above:

 

Now, let’s remove node with value 31.

As you can see, tree is unbalanced. Node with value 45 (root node) has child nodes with levels 1 and 3… so we mark node 45 as node z. Node 60 is child node of z with higher level, so that one will be y node. Child nodes of y both have same levels… rule is: pick one. If you pick 51 as x, you will have case 3 – double rotation; if you pick 75 as x, you will have case 1 – single rotation. Case 1 seems simpler and easier on resources, so I will pick case 1 and make node with value 75 to be x:

 

Not shown on image above:

• T0 = Left child of z (45): 17 (with it’s child nodes)
• T1 = Left child of y (60): 51 (with it’s child nodes)
• T2 = Left child of x (75): null node
• T3 = Right child of x (75): 78 (with it’s child nodes)

When we apply algorithm restructure(x) we get balanced tree:

Not shown on image above:

• T0 = Left child of z (45): 17 (with it’s child nodes)
• T1 = Right child of z (45): 51 (with it’s child nodes)
• T2 = Left child of x (75): null node
• T3 = Right child of x (75): 78 (with it’s child nodes)

There are many other types of trees: multi-way search trees; (2,4) trees; red-black trees; splay trees; etc. Each of them has good and bad sides… and you need to know those data structures, and how you can benefit (or not) by using them.

For balanced trees, as you already see, they give log n performance for find(x), insert(x), remove(x) element. But the performance hit is when tree needs to be re-balanced. So if you will have tree mostly used for search, I recommend balancing your tree… but if you will have frequent insertion/removals, then frequent balancing might be needed, and you will not gain such a good performance…

Next: Data Structures — Part 7 (Priority Queue and Heap)

Data Structures — Part 5 (Traversing Trees)

Tree structures can be traversed in many different ways. Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed define the traversal type. These steps are:

• performing an action on the current node (referred to as "visiting" the node),
• traversing to the left child node, and/or
• traversing to the right child node.

The process is most easily described through recursion. I will discuss three most common ways of traversing a tree.

To traverse a non-empty binary tree in preorder (depth-first traversal), perform the following operations recursively at each node, starting with the root node:

1. Visit the node.
2. Go left.
3. Go right.

Sample implementation (assumes that tree is non-empty):

preorder(Node node){

  Console.WriteLine(node.value);

  if (!node.left==null) preorder(node.left);

  if (!node.right==null) preorder(node.right);

}

Order of visiting this tree in preorder will be: 25, 15, 4, 17, 16, 20, 45, 31, 48, 47.

To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node, starting with the root node:

1. Go left.
2. Visit the node.
3. Go right.

Sample implementation (assumes that tree is non-empty):

inorder(Node node){

  if (!node.left==null) then inorder(node.left);

  Console.WriteLine(node.value);

  if (!node.right==null) then inorder(node.right);

}

Order of visiting this tree in inorder will be: 4, 15, 16, 17, 20, 25, 31, 45, 47, 48.

To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node, starting with the root node:

1. Go left.
2. Go right.
3. Visit the node.

Sample implementation (assumes that tree is non-empty):

postorder(Node node){

  if (!node.left==null) then postorder(node.left);

  if (!node.right==null) then postorder(node.right);

  Console.WriteLine(node.value);

}

Order of visiting this tree in postorder will be: 4, 16, 20, 17, 15, 31, 47, 48, 45, 25.

Next: Data Structures — Part 6 (Balanced Trees)

Arrays

An array is a data structure that contains a number of variables of the same type. Arrays are zero-based – first element is labeled with 0.

Arrays can have countless dimensions. Examples:

• Single-dimensional: type[] name;
• Two-dimensional: type[,] name;
• Multidimensional: type[,,…] name;
• Jagged (array of arrays): type[][] name;

Every element of array has index and value. Single-dimensional array with string elements: Steve, Alan, Sean, Bill, Ryan can be represented as:

To create array you need to indicate type, [] and name of array. Example:

int[] numbers;

Will create array "names" of type int. When you want to store elements in the array you need to use new:

numbers = new int[] { 1, 2 , 3, 4, 7, 8 };

You can also have this in the same line as:

int[] numbers = new int[] { 1, 2 , 3, 4, 7, 8 };

Sample for Single-dimensional array (declare/initialize/print):

public void SimpleArray() {

    int[] numbers = {1, 2, 3, 5, 7};

    foreach (int i in numbers) {

        Console.WriteLine("Array member: " + i.ToString());

    }

}

Output of code above will be:

Array member: 1

Array member: 2

Array member: 3

Array member: 5

Array member: 7

***********************************************************

If you have array:

int[] numbers = {1, 2, 3, 5, 7};

you have actually:

numbers[0]=1; numbers[1]=2; numbers[2]=3; numbers[3]=5; numbers[4]=7;

and if you give command:

numbers[2] = 9;

then array will look like:

numbers = 1, 2, 9, 5, 7;

Note that numbers[2] was initially 3, but then with your command it was set to 9.

 

Sample for Two-dimensional array (declare/initialize/print):

public void TwoDimArray() {

    string[,] people = new string[3, 2] { //Indicates that there are 3 'rows' and 2 'columns'

        {"Sonja", "S"},

        {"Martin", "N"},

        {"Sean", "G"},

    }; 

    for (int i=0; i<3; i++) { 

        Console.Write("First name: " + people[i,0].ToString()); //Print first element

        Console.WriteLine(" Last name: " + people[i, 1].ToString()); //Print second element

    }

} 

You can imagine array in TwoDimArray() as matrix:

	Element 1	Element 2
Row 1	[0,0]=Sonja	[0,1]=S
Row 2	[1,0]=Martin	[1,1]=N
Row 3	[2,0]=Sean	[2,1]=G

Output of code above will be:

First name: Sonja   Last Name: S

First name: Martin   Last Name: N

First name: Sean   Last Name: G

 

Looking at the two-dimensional array you have idea how you would create and work with three, four, etc. dimensional array.

Sample for jagged array (declare/initialize/print):

int[][] jag = new int[][] {new int[] {1, 2, 3, 4}, new int[] {5, 6, 7, 8}};

for (int i = 0; i < jag.GetLength(0); i++) {

    for (int j = 0; j < jag[i].GetLength(0); j++) {

        Console.WriteLine(jag[i][j].ToString());

    }

}

Output of code above will be:

1 2 3 4 5 6 7 8

I believe that this covers basics on arrays…

Data Structures — Part 4 (Trees)

Trees are data structure created out of nodes which have values and pointers/references to other/child nodes. For binary trees, each node can point to up to two child nodes: left and right. If node does not have left and/or right child node, it will point to null. 

  

Node of binary tree

Here is sample how to create node for binary tree:

class Node {        

    int val;        

    Node LeftChild;        

    Node RightChild;         

    Node(int val, Node LeftChild, Node RightChild){            

        this.val=val;

        this.LeftChild=LeftChild;

        this.RightChild=RightChild;        

    }    

}

Starting (first) node is called "Root Node". Other nodes are added to the tree by following rules:

1. If current node = null, then current node = new node
2. Else:
   • if new node is < than current node then go left
   • if new node is > than current node then go right

Let’s try to explain this with sample… Tree below is created with inserting numbers: 15, 8, 19, 34, 56, 5, 20.

Let’s now add 27 to the tree:

• Root not null… 
• 27 > 15 => go right … Node not null… 
• 27 > 19 => go right … Node not null… 
• 27 < 34 => go left … Node not null… 
• 27 > 20 => go right … Node == null…  => add 27 to the tree (20 right will point to new node with value=27; L=null; R=null)

As you can see from samples above, tree is a data structure which will sort your data, for free, as elements are inserted… this can be useful for search. Trees (like these in sample above) don’t support duplicate values.

Trees are not so dandy if you are entering elements in sorted order, like: 1, 5, 8, 15, 23, etc. then you get a tree which is actually sorted array – but it takes more space in memory because of (in this example) ‘left’ which is actually not used.

Of course, this is worst case scenario… but something similar might happen. This is where balanced trees come into picture… but more about them later….

I showed you how to insert node in a tree… now, how to remove node from a tree? This is where we can distinguish tree cases:

• CASE 1: If both children of node which needs to be removed is external node (null). Then we remove that node by making his parent point to null instead to that node.
• CASE 2: If one of the children of node which needs to be removed is external node (null). See sample – we want to remove node with value 20, let’s call it "Node A"… this is how tree looks like:

In this case, child node of Node A will become child node of parent node for Node A:

• CASE 3: If both children of node which needs to be removed are internal nodes. See sample – we want to remove node with value 34, let’s call it "Node A"… this is how tree looks like:

We need to find first internal node that follows Node A in an inorder traversal of the tree. (I will talk about inorder traversal of tree later)… That internal node, let’s call it Node B will be the left-most internal node in the right subtree of Node A, and is found by going first to the right child of Node A, and then down from there following left children.

Node B will replace Node A; right child of Node B (if any) will replace Node B – in this sample, right child node of B is marked green. This is how the resulting tree will look like:

I know, I know… you are probably wondering "and how to implement this?"… Well, it’s very similar as with Linked Lists – you need to take care of pointers/references (Left/Right) for appropriate nodes. For this example:

• (Node A parent).Right will point to Node B
• (Node B parent).Left will point to Node B.Right
• Node A.Left will be Node B.Left
• Node A.Right will be Node B.Right

Garbage collector will take care of the rest (removing nodes which are not used any more).

In this post I explained what are trees, how to add/remove nodes from a tree. Next will follow description of different ways how to traverse a tree and more about balanced trees…

Next: Data Structures — Part 5 (Traversing Trees)

Data Structures — Part 3 (Linked Lists)

Lists are nodes which have values and pointers/references to each other – each node will point to some other node.

Node for doubly linked list

Here is sample how you can create your own Node for doubly linked list:

class Node

    {

        String val;

        Node Next;

        Node Previous;

        Node(Node Next, String val, Node Previous)

        {

            this.Next=Next;

            this.val=val;

            this.Previous=Previous;

        }

    }

Linked lists can contain sentinel nodes, such as header (at the beginning of the list) and/or trailer (at the end of the list). These nodes will not contain any value, they will contain only pointers to next node (for header) and/or pointer to previous node (trailer).

Header node – will have only pointer to the Next node (first node in the list). Previous will have value NULL. Purpose of having Header is to mark beginning of the list.

Trailer node – will have only pointer to the Previous node (last node in the list). Next will have value NULL. Purpose of having Trailer is to mark end of the list.

 

  

Doubly Linked List with Header and Trailer

When looking at the nodes, linked lists can be:

• single linked lists – nodes have value and pointer to Next node; this means that each node has information about next node in the list; this list can be traversed in only one direction: from beginning until the end.

Sample of single linked list

• doubly linked lists – nodes have value and pointers to Next and Previous node; this means that each node has information about next and previous node in the list; this list can be traversed in both directions.

Sample of doubly linked list

Note: For examples below I will be using doubly linked list… once you get the principle for doubly linked list, it’s easy to get it how it works for single linked list.

When looking at the structure which nodes are creating, linked lists can be:

• linearly-linked – when traversing the list, no nodes are getting visited two times; when looking at the list, it looks like straight line. This type of linked list can optionally have header and/or trailer.
• circular linked – when traversing the list, at certain point, you will revisit already visited node; when looking at the list it looks that it has a loop (circle). This type of linked list will not have trailer, while header is optional.

Sample of circular doubly linked list

Some of common linked list methods:

• Replace element (p, e) – replace element on position p with element e
• Swap elements (p, q) – swap elements p and q
• Insert first (e) – insert element e as first one in the list
• Insert last (e) – insert element e as last one in the list
• Insert before (p, e) – insert element e before position p
• Insert after (p, e) – insert element e after position e
• Remove (p) – remove element p

Algorithm insert after (p, e):

//create new node newNode with (prev, val, next)

1:   newNode.val := e;

2:   newNode.prev := p;

3:   newNode.next := p.next;

4:   (newNode.next).previous := newNode;

5:   p.next := newNode;

Let me show what is happening here visually so that you can have better idea:

New node is created and it has value e

Previous node for the newNode will be node in position p

Next node for the newNode will be node in position p.next; Note that at this point, p.next is now the same as newNode.next

Previous node for newNode.next is newNode; this will overwrite previous where (p.next).previous = p

  

Next node for p is newNode; this will overwrite previous value of p.next

 

Algorithm remove (p):

1:   (p.prev).next := p.next;

2:   (p.next).prev := p.prev;

3:   p.prev := null;

4:   p.next := null;

OK. Now let’s put this one into pictures also:

Next node for p.previous is p.next; this will overwrite previous value of p.next

Previous node for p.next is p.previous; this will overwrite previous value of p.previous

p does not have previous node

p does not have next node   

We don’t need to think further about removing node p – that will be handled by garbage collector.

Next: Data Structures — Part 4 (Trees)

Data Structures — Part 2 (Queues)

Queue is a data structure with FIFO (First In First Out) principle.

You can imagine queue as a vertical pipe with open top and bottom; and you can put objects inside pipe from the top and getting them out from the bottom.

Below you can see samples of queue with objects A, B and C (entered in that order); and you want to add object D to the queue:

 

Add object to the queue

Now you have queue with objects A, B, C and D (entered in that order) and you want to remove one object. Note that you don’t have choice which object to remove, since you can remove only object from the bottom of the queue (the first object entered):

 

Remove object from the queue

Some of common queue methods:

• enqueue(o) – insert object o in the queue
• dequeue() – remove object from the queue and return object on the front of queue; an error occurs if queue is empty
• size() – return the number of objects in the queue
• isEmpty() – return Boolean (true/false) indicating if the queue is empty
• front() – return object in front of the queue (without removing it); an error occurs if queue is empty
• isFull() – return Boolean (true/false) indicating if the queue is full

Algorithm enqueue(o):

if size() == N - 1 then

    //indicate that queue is full and throw an error

else

    Q[t] := o //next element in queue is o

    t := t + 1 //increment number of objects in queue

Data Structures — Part 3 (Linked Lists)… Coming soon…

Data Structures — Part 1 (Stacks)

Stack is a data structure with LIFO (Last In First Out) principle.

You can imagine stack as a vertical pipe with open top and closed bottom; and you can put objects inside pipe from the top and getting them out from the top.

Below you can see samples of stack with objects A, B and C (entered in that order); and you want to add object D to the stack:

Add object to the stack

Now you have stack with objects A, B, C and D (entered in that order) and you want to remove one object. Note that you don’t have choice which object to remove, since you can remove only object from the top of the stack (the last object entered):

 

Remove object from the stack

Some of common stack methods:

• push(o) – insert object o to the stack
• pop() – remove object from the stack and return top object on the stack; an error occurs if stack is empty
• size() – return the number of objects in the stack
• isEmpty() – return Boolean (true/false) indicating if the stack is empty
• top() or peek() – return top object on the stack (without removing it); an error occurs if stack is empty
• isFull() – return Boolean (true/false) indicating if the stack is full

Algorithm push(o):

if size() == N then

    //indicate that stack is full and throw an error

else

    t:=t+1  //increment number of elements in stack

    S[t] := o  //newest element of stack S is object o

Algorithm pop():

if isEmpty() then

    //indicate that stack is empty and throw an error

else

    e:=S[t] //e is set to value of object on the top of the stack

    S[t]:=null //object on the top of the stack is set to null

    t:=t-1  //decrement number of elements in stack

    return e //return what was removed from stack

Data Structures — Part 2 (Queues)… Coming soon…