Linked List Based Implementation of Stack and Queue

Why different implementations

• The way the data structure is implemented is a measure of its efficiency (time and space)
  
• It is important to see different alternatives
  
• So far we have discussed array based implementation (vector). What if we use second class arrays?
  

Objectives:
Discuss linked list based implementation of stack and queue.
Compare and contrast two implementations

Linked List based Stack

• Stack is LIFO data structure
  
  
  
  
  
  
  
  
  
• Linked list is a collection of nodes where each node has a data element and a pointer to the next element in the list.
  
  

Linked List based Stack- basic concepts

• Stack we push into and pop from the top of the stack.
  
• Therefore a special pointer “toOftheStack” which is pointing to the top of the stack is created.
  
• Intially toOftheStack is null.
  
• Try following operations
  
• push (a), push(b), push(c)
  
• pop()
  

Linked List based Stack- C++ Details
A Node: (figure 16.19)

struct ListNode
{
Object element;
ListNode *next;
ListNode ( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { }

};

Linked List based Stack- C++ Details
Template
template <class Object> class Stack {
public:
Stack( );
Stack( const Stack & rhs );
~Stack( ); bool isEmpty( ) const;
const Object & top( ) const;
void makeEmpty( );
void pop( );
void push( const Object & x );
Object topAndPop( );
const Stack & operator=( const Stack & rhs );

private:
struct ListNode { Object element; ListNode *next; ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { } };

ListNode *topOfStack; };

Linked List based Stack- C++ Details
Implementation
Stacklist.cpp
push, pop, top, makeEmpty and = operator

Linked List based Queue

• Queue if FIFO data structure
• Implementation is very similar to stack. Here, both from and back of the data structure need pointers.

Linked List based Queue- basic concepts

• Queue, enqueue into the front of the stack. Dequeue from the back of the stack
• Therefore two special pointers “front,” and “back,” are created.
• Initially both both front and back are null.
• Try following operations
• enqueue (a), enqueue(b), enqueue(c)
• dequeue()

Linked List based Queue - C++ Details
A Node:

struct ListNode {
Object element;
ListNode *next;
ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n )
{ }
};

Linked List based Queue - C++ Details
Template
Queuelist.h
Notice that there are two pointers, front and back

Linked List based Queue - C++ Details
Implementation
Queuelist.cpp
Enqueue, dequeue, copy constructure and = operator

Array base vs. Linked list based Implementation

• For large size stacks and queue specially the size is not known linked list is better.
• For memory scare devices such as small handheld devices, linked list may perform better.

Algorithms & Data Structures - Linked List

Objectives
At the end of the class you should be able to answer:

Explain the design, use, and operation of a linear list

Implement a linear list using a linked list structure

Understand the operation of the linear list ADT

Write application programs using the linear list ADT

Design and implement different link-list structures

Basic Operations
The four basic list operations are :

1. Insertion
2. Deletion
3. Retrieval
4. Traversal

Insertion

• Insertion is used to add a new element to the list.
• List insertion can be ordered or random.
• Ordered list are maintained in sequence according to the data or, when available, a key that identifies the data.
• In random lists there is no sequential relationship between two elements.Random lists are sometimes called chronological lists.

Figure 5-1 Shows the insertion of data into a list



Deletion

• Deletion is used to remove an element from the list.
• Deletion from a list requires that the list be searched to locate the data being deleted
• Once located, the data are removed from the list.

Figure 5-2 Shows the Deletion operation


Retrieval

• Retrieval is used to get the information related to an element without changing the structure of the list.
• List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the list.

Figure 5-3 Shows retrieving data from a list



Traversal

• List traversal processes each element in a list in sequence
• It requires a looping algorithm rather than a search.

Implementation

• Several data structures can be used to implement a list; we use a linked list.
• Linked list is a good structure for a list because data are easily inserted and deleted at the beginning, in the middle, or at the end of the list.

Data Structure
To implement a list, we need two different structures, a head node and data node.


Figure 5-5 Shows a head node and data node



Algorithm
Create List:
Create list allocate the head structure and initializes the metadata for the list.
Figure 5-6 shows the header before and after it is initialized by create list.


Figure 5-6 Create list



Algorithm for creating a list



Insert Node
Insert node adds data to a list. Given the predecessor, there are three steps to the insertion:
1. Allocate memory for the new node and move data to the node.
2. Point the new node to its successor.
3. Point the new node’s predecessor to the new node.


Figure 5-7 Add node to empty list



Insert at Beginning

• To insert a node at the beginning of the list, we simply point the new node to the first node of the list and then ser the head pointer to point to the new first node.
• Figure 5-8 shows inserting a node at the beginning

Figure 5-8 Shows Add node at Beginning



Insert in Middle

• To insert a node between two nodes, we point the new node to its successor and then point its predecessor to the new node.
  
• Figure 5-9 shows inserting a node in the middle.
  

Figure 5-9 Add node in Middle



Insert at End

• To add at the end of the list, we only need to point the predessor to the new node.
  
• The Figure5-10 insert the node at the end
  

Figure 5-10 Add node at End



Algorithm for Insertion is shown in figure 5-2



Delete Node

• The delete node algorithm logically removes a node from the list by changing various link pointers and then physically delete the node from dynamic memory.
  
• Figure 5-11 shows Deleting the first node
  

Delete First Node



Algorithm for Deleting a node


Retrieve Node
Figure 5-5 Shows retrieve list node algorithm








Advance Linked List

• Circular Linked List
  
• Circular linked list is a type of linked list where the last node will point back to the first node
  

Graphical view of a circular linked list

Algorithms & Data Structures - Heap

A priority queue is a special type of queue where items with special characteristic are removed from the list first.

Heap is a priority queue data structure.

heap is a structure that fulfils two properties:

1.Shape (no hole)
A heap must be a complete tree.

2.Order of its element
The value stored in each node of the heap must be greater than, less than, or equal to the value of its children, depending on what type of heap it is.


Nodes in a heap are filled from left to right, and we cannot proceed to the next lower level of the tree until all nodes in that particular level are filled.


There are two types of heaps:

Ascending heap

This is a heap in which the values of the parent's nodes are smaller than or equal to the value of the children's nodes.



Descending heap

This is a heap in which the value of the parent's nodes are greater than or equal to the value of the children's nodes




Example:
Given these data: 17, 8, 12, 4, 26, 5, 14.
Build a descending and ascending Heap


BINARY HEAP

The binary heap is the classic method used to implement priority queues.

A binary heap is a binary tree that, except for the bottommost level, is completely filled from left to right.



HEAP SORT

A heapSort is a method of sorting an array of items of no particular order into an array of certain order.

Applicable to its name, this method uses a heap to facilitate sort operations.

Operations with HEAPSORT

• Insertion
• Deletion
• delete Min
• delete Max

Insertion

REHEAP UP CONCEPT

Delete Min

Coding : check previous courseware

Delete Max
Involved descending heap


Exercise 1:
Given the following numbers, build an ascending and descending heap.

8, 54, 43, 3, 77, 89, 21, 23, 5, 40

Perform deletemin for the ascending heap and deletemax for the descending heap

Exercise 2:
Use heapsort to sort the numbers into ascending list.

8, 54, 43, 3, 77, 89, 21, 23, 5, 40