Linked List Implementation

Linked List Implementation

1. Stack Concept 

•Stack is an important data structure which stores its elements in an ordered manner

   Stack is a linear data structure which can be implemented by either

   using an array or linked list. The elements in a stack are added and

   removed only from one end, which is called the top. The data are 

   stored in Last In First Out (LIFO) way.

Linked List Representation

Technique of creating a stack using array is easier, but the drawback is that the array must 

be declared to have some fixed size. In a linked stack, every node has two parts:

–One that stores data

–One that stores the address of the next node

•The START pointer of the linked list is used as TOP

•All insertions and deletions are done at the node pointed by the TOP

•If TOP = NULL, then it indicates that the stack is empty

Stack Operations

•push(x)  : add an item x to the top of the stack.

•pop()  : remove an item from the top of the stack.

•top()  : reveal/return the top item from the stack.

Example :

2. Stack Applications

There are three arithmetic notations known:

•Prefix notation, also known as Reverse Polish notation.

•Infix notation (commonly used)

•Postfix notation, also known as Polish notation.

Example :

Prefix  : * 4 10

Infix    : 4 * 10

Postfix: 4 10 *

Infix Evaluation

Evaluate a given infix expression: 4 + 6 * (5 – 2) / 3

To evaluate infix notation, we should search the highest precedence

operator in the string.

4 + 6 * (5 – 2) / 3  search the highest precedence operator, it is ( )

4 + 6 * 3 / 3  search the highest precedence operator, it is *

4 + 18 / 3  search the highest precedence operator, it is  /

4 + 6  search the highest precedence operator, it is +

10

Postfix Evaluation

Manually

Scan from left to right

7   6   5   x   3   2   ^   –    +  , scan until reach the first operator

7   6   5   x   3   2   ^   –    +  , calculate 6 x 5

7   30           3   2   ^   –    +  , scan again until reach next operator

7   30           3   2   ^   –    +  , calculate 32

7   30           9             –    +  , scan again to search next operator

7   30           9             –    +  , calculate 30 – 9

7   21                                +  , scan again

7   21                                +  , calculate 7 + 24

28    , finish

String  

  4 6 5 2 – * 3 / +

  4 6 5 2 – * 3 / +  4  push(4)

  4 6 5 2 – * 3 / +  4 6  push(6)

  4 6 5 2 – * 3 / +  4 6 5  push(5)

  4 6 5 2 – * 3 / +  4 6 5 2  push(2)

  4 6 5 2 – * 3 / +  4 6 3  pop 2, pop 5, push(5 – 2)

  4 6 5 2 – * 3 / +  4 18  pop 3, pop 6, push(6 * 3)

  4 6 5 2 – * 3 / +  4 18 3  push(3)

  4 6 5 2 – * 3 / +  4 6  pop 3, pop 18, push(18 / 3)

  4 6 5 2 – * 3 / +  10  pop 6, pop 4, push(10) à  the result

Prefix Evaluation

Manually

Scan from right to left

+   7   –   x   6   5   ^   3   2

+   7   –   x   6   5   ^   3   2

+   7   –   x   6   5   9

+   7   –   x   6   5   9 

+   7   –   30           9

+   7   –   30           9

+   7   21

+   7   21

28

Conversion : Infix to Postfix

•Manually

•A + B – C x D ^ E / F   , power has the highest precedence

•A + B – C x D E ^ / F   , put ^ behind D and E

•A + B – C x D E ^ / F   , x  and / have same level precedence

•A + B – C D E ^ x / F   , put x at the end

•A + B – C D E ^ x / F   , continue with the same algorithm till finish

•A + B – C D E ^ x F /

•A + B – C D E ^ x F /

•A B + – C D E ^ x F /

•A B + – C D E ^ x F /

•A B + C D E ^ x F / –   , this is the Postfix notation

String                             Stack             Postfix String

 4 + 6 * (5 – 2) / 3 

 4 + 6 * (5 – 2) / 3                                          4

 4 + 6 * (5 – 2) / 3              +                          4

 4 + 6 * (5 – 2) / 3              +                          4 6

 4 + 6 * (5 – 2) / 3              + *                       4 6

 4 + 6 * (5 – 2) / 3              + * (                     4 6

 4 + 6 * (5 – 2) / 3              + * (                     4 6 5

 4 + 6 * (5 – 2) / 3              + * ( –                  4 6 5

 4 + 6 * (5 – 2) / 3              + *                       4 6 5 2

 4 + 6 * (5 – 2) / 3              + * /                     4 6 5 2 –

 4 + 6 * (5 – 2) / 3              + /                        4 6 5 2 – *

 4 + 6 * (5 – 2) / 3              + /                        4 6 5 2 – * 3

 4 + 6 * (5 – 2) / 3                                           4 6 5 2 – * 3 / +

Conversion : Infix to Prefix

Manually

A + B – C x D ^ E / F

A + B – C x ^ D E / F

A + B – C x ^ D E  / F

A + B – x C ^ D E  / F

A + B – x C ^ D E / F

A + B – / x C ^ D E F

A + B – / x C ^ D E F

+ A B – / x C ^ D E F

+ A B – / x C ^ D E F

– + A B / x C ^ D E F  , this is the Prefix notation

3. Depth Search

Depth First Search (DFS) is an algorithm for traversing or searching in a tree or graph. We start at the root of the 

tree (or some arbitrary node in graph) and explore as far as possible along each branch beforebacktracking.

DFS has many applications, such as:

•Finding articulation point and bridge in a graph

•Finding connected component

•Topological sorting

•etc.

DFS can be implemented by a recursive function or an iterative procedure using stack, their results may have a 

little differences on visiting order but both are correct.

Algorithm:

Prepare an empty stack

Push source/root into stack

Mark source/root

While stack is not empty

  Pop an item from stack into P

  For each node X adjacent with P

  If X is not marked

  Mark X

  Push X into stack

4. Queue

Queue can be implemented by either using arrays or linked lists. The elements in a queue

 are added at one end called the rear and removed from the other one end called front. The 

data are stored in First In First Out (FIFO) way, this is the main difference between stack

and queue

•push(x)  : add an item x to the back of the queue.

•pop()  : remove an item from the front of the queue.

•front()  : reveal/return the most front item from the queue.

(front is also known as peek.)

Cicular Queue

•We can wrap-around index L and R.

•If R reach MAXN then set R as zero, do the same to L.

•It is also known as circular queue.

Deques

A deque (pronounced as ‘deck’ or ‘dequeue’) is a list in which elements can be inserted

or deleted at either end. It is also known as a head-tail linked list, because elements can 

be added to or removed from the front (head) or back (tail).

Two variants of a double-ended queue, include:

•Input restricted deque

  In this dequeue insertions can be done only at one of the dequeue while deletions can be done

  from both the ends.

•Output restricted deque

  In this dequeue deletions can be done only at one of the dequeue while insertions can be done

  on both the ends.

Priority Queue

A priority queue is an abstract data type in which the each

element is assigned a priority.

The general rule of processing elements of a priority queue

can be given as:

•An element with higher priority is processes before an element with lower priority

•Two elements with same priority are processed on a first come first served (FCFS) basis

5. Breadth First Search

Breadth First Search (BFS) like DFS is also an algorithm for traversing or searching in a 

tree or graph. We start at the root of the tree (or some arbitrary node in graph) and explore 

all neighboring nodes level per level until we find the goal.

BFS has many applications, such as:

•Finding connected component in a graph.

•Finding shortest path in an unweighted graph.

•Ford-Fulkerson method for computing maximum flow.

•etc

The difference between DFS and BFS iterative implementation is only the data structure 

being used.

DFS uses stack while BFS uses queue.

Algorithm:

Prepare an empty queue

Push source/root into queue

Mark source/root

While queue is not empty

  Pop an item from queue into P

  For each node X adjacent with P

  If X is not marked

  Mark X

  Push X into queue