Revisiting a data structures in detail with linked list stack and queue

DataStructure • A data structure is a process of organizing the data elements in the memory of a computer. Data Structure Linear Non-Linear - Array - Stack - Queue - Linked Lists - Trees - Graphs

Array • 1.Array : • An array is a collection of homogeneous type of data elements. • 2. Array Interfaces / • Functionalities of Array • Traversing • Search • Insertion • Deletion • Sorting • Merging

Inserting the data element into anArray

#include<iostream> using namespace std; int main() { int i,a[50],no,pos,size; cout<<"Enter array size( Max:50 ) :: "; cin>>size; cout<<"nEnter array elements :: n"; for(i=0; i<size; i++) { cout<<"nEnter arr["<<i<<"] Element :: "; cin>>a[i]; } cout<<"nStored Data in Array :: nn"; for(i=0;i<size;i++) { cout<<" "<<a[i]<<" "; } cout<<"nnEnter position to insert number :: "; cin>>pos; if(pos>size) { cout<<"nThis is out of range.n"; } else { cout<<"nEnter number to be inserted :: "; cin>>no; --pos; for(i=size;i>=pos;i--) { a[i+1]=a[i]; } a[pos]=no; cout<<"nNew Array is :: nn"; for(i=0;i<size+1;i++) { cout<<" "<<a[i]<<" "; } } cout<<"n"; return 0; }

Deleting the data element from an array

#include<iostream> #include<conio> void main() { int arr[50], size, i, del, count=0; cout<<"Enter array size : "; cin>>size; cout<<"Enter array elements : "; for(i=0; i<size; i++) { cin>>arr[i]; } cout<<"Enter element to be delete : "; cin>>del; for(i=0; i<size; i++) { if(arr[i]==del) { for(int j=i; j<(size-1); j++) { arr[j]=arr[j+1]; } count++; break; } } if(count==0) { cout<<"Element not found..!!"; } else { cout<<"Element deleted successfully..!!n"; cout<<"Now the new array is :n"; for(i=0; i<(size-1); i++) { cout<<arr[i]<<" "; } } getch(); }

Stack • A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc.

Stack Representation • Can be implemented by means of Array, Structure, Pointers and Linked List. • Stack can either be a fixed size or dynamic.

Stack usingArray • Push Operation top top PUSH Pop Operation top top POP

Stack usingArray top ++top top push pop top top top--

StackAlgorithms Algorithm size() return top +1 Algorithm pop(S[],top,item) if top=-1 then print “ stack is underflow” else top top - 1 return S[top+1] Algorithm push(S[],item, max, top) if top = max-1 then print “ stack is full” else top  top + 1 S[top]  item

Queue • Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue).

Queue Representation • As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and Structures.

Algorithm enqueue(o) if rear = N-1 then print “queue full error” else if(front =-1) front=0 r (f + sz) mod N Q[r]  o sz (sz + 1) Algorithm isfull() return sz=N Algorithm size() return sz Algorithm isEmpty() return (sz ==0) Algorithm dequeue() if front=rear then print “ Queue is empty” else o Q[f] f  (f + 1) mod N sz (sz - 1) if (front==rear) front=rear=-1 return o

Linked list • Linear collection of self-referential class objects, called nodes Connected by pointer links • Accessed via a pointer to the first node of the list • Link pointer in the last node is set to null to mark the list’s end • Use a linked list instead of an array when • You have an unpredictable number of data elements • You want to insert and delete quickly.

Singly Linked List • A singly linked list is a concrete data structure consisting of a sequence of nodes • Each node stores • element • link to the next node Last element points to NULL. It does not waste memory space. It can grow or shrink in size during execution of a program. next elem node A B C D 

Linked List • Keeping track of a linked list: • Must know the pointer to the first element of the list (called start, head, etc.). • Basic operations commonly include: • Construction: Allocate and initialize a list object (usually empty) • Empty: Check if list is empty • Insert: Add an item to the list at any point • Delete: Remove an item from the list at any point • Traverse: Go through the list or a part of it, accessing and processing the elements in the order they are stored

Basic Linked ListOperations • List Traversal (Display function) • Searching an element in a linked list • Insert a node (At begin, At end , In between) • Delete a node (At begin, At end , In between)

Create a Linked List • Empty Linked list is a single pointer having the value of NULL. head = NULL; • Let’s assume that the node is given by the following type declaration: struct node{ int data; struct node *next; }; • To start with, we have to create a node (the first node), and make head point to it. head= (struct node*)malloc(sizeof(struct node)); free(head); //malloc() head= new (struct node); or head=new node; //C++ delete head;//C++ head head Data next

Singly linked lists Node Structure struct node { int data; struct node *link; }*new1, *ptr, *header, *ptr1; Creating a node new1 = malloc (sizeof(struct node)); new1= new (struct node); //C++ new1  data = 10; new1  link = NULL; data link 2000 10 new 2000 NULL

Inserting a node at the beginning Create a node that is to be inserted 2500 data link 10 new1 2500 NULL Algorithm: 1. Create a new node. 2.if (header = = NULL) 3. header = new; 4.else 5.{ 6. new  link = header; 7. header = new; 8.} If the list is empty NULL header header If the list is not empty 1200 header 2500 10 new 2500 NULL 1200 1300 1330 1400 NULL 5 5 4 8 1300 1330 1400

Inserting a node at the end 10 1800 20 1200 30 1400 40 NULL 1500 1800 1200 1400 1500 header 50 NULL 2000 Algorithm: 1. new1=new (struct node)); 2. ptr = header; 3. while(ptr  link!= NULL) 4. ptr = ptr  link; 5. ptr  link = new1; 2000 new 1500 ptr 1800 1200 1400 2000

Inserting a node at the given position 10 1800 20 1200 30 1400 40 NULL 1500 header 50 NULL 2000 2000 new Algorithm: 1. new1=new (struct node); 2. ptr = header; 3. for(i=1;i < pos-1;i++) 4. ptr = ptr  link; 5. new1  link = ptr  link; 6. ptr  link = new1; 1500 ptr 1500 1800 1200 1400 Insert position : 3 1800 1200 2000

Deleting a node at the beginning Algorithm: 1. if (header = = NULL) 2. print “List is Empty”; 3. else 4. { 5. ptr = header; 6. header = header  link; 7. free(ptr); 8. } 10 1800 20 30 1400 40 NULL 1500 1800 1200 1400 1200 1500 header 1500 ptr 1800

Deleting a node at the end 10 1800 20 1200 30 1400 40 NULL 1500 1800 1200 1400 1500 header Algorithm: 1. ptr = header; 2. while(ptr  link != NULL) 3. ptr1=ptr; 4. ptr = ptr  link; 5. ptr1  link = NULL; 6. free(ptr); 1500 ptr 1800 1200 NULL ptr1 ptr1 ptr1 1400

Deleting a node at the given position 10 1800 20 1200 30 1400 40 NULL 1500 header Algorithm: 1. ptr = header ; 2. for(i=1;i<pos-1;i++) 3. ptr = ptr  link; 4. ptr1 = ptr  link; 5. ptr  link = ptr1 link; 6. free(ptr1); 1500 ptr 1500 1800 1200 1400 Delete position : 3 1800 ptr1 1200 1400

Traversing an elements of a list 10 1800 20 1200 30 1400 40 NULL 1500 1800 1200 1400 1500 header Algorithm: 1. if(header = = NULL) 2. print “List is empty”; 3. else 4. for (ptr = header ; ptr != NULL ; ptr = ptr  link) 5. print ptr  data; ptr 1500

Searching an element in a linked list Algorithm: Step 1: SET ptr = header Step 2: Set I = 0 STEP 3: IF ptr = NULL WRITE "EMPTY LIST" GOTO STEP 8 STEP 4: REPEAT STEP 5 TO 7 UNTIL PTR != NULL STEP 5: if ptr → data = item write i+1 //goto step 8 STEP 6: I = I + 1 STEP 7: PTR = PTR → NEXT STEP 8: EXIT

Creating the linked List struct Node { int data; struct Node *next; }; void main() { struct Node *head; head=create_list(); display(head); } struct Node *create_list() { int k, n; struct Node *p, *Head; printf("n How many elements to enter?"); scanf("%d", &n); for (k=0; k<n; k++) { if (k == 0) { Head = (struct Node*)malloc(sizeof(struct Node)); p = Head; } else { p->next = (struct Node*)malloc(sizeof(struct Node)); p = p->next; } printf("n Enter an %dth element",k); scanf("%d",&p->data); } p->next = NULL; return(Head); } void display (struct Node *head) { struct Node *p; for(p = head; p!= NULL; p = p->next) { printf ("nNode data %d", p->data); } printf ("n"); } #include<stdio.h> #include<stdlib.h> struct Node *create_list(); void display(struct Node *);

COMPLEXITYOFVARIOUSOPERATIONS IN ARRAYSAND LINKED LIST

Algorithms –PUSH & POP • Algorithm PUSH (value) • Step 1 - Create a newNode with given value. • Step 2 - Check whether stack is Empty (top == NULL) • Step 3 - If it is Empty, then set newNode → next = NULL. • Step 4 - If it is Not Empty, then set newNode → next = top. • Step 5 - Finally, set top = newNode. • Algorithm POP • Step 1 - Check whether stack is Empty (top == NULL). • Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function • Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'. • Step 4 - Then set 'top = top → next'. • Step 5 - Finally, delete 'temp'. (free(temp)).

void display() { struct Node* ptr; if(top==NULL) cout<<"stack is empty"; else { ptr = top; cout<<"Stack elements are: "; while (ptr != NULL) { cout<< ptr->data <<" "; ptr = ptr->next; } } cout<<endl; } #include <iostream> using namespace std; struct Node { int data; struct Node *next; }; struct Node* top = NULL; struct Node* temp = NULL; void push(int val) { struct Node* newnode = new node; newnode->data = val; newnode->next = top; top = newnode; } void pop() { temp = top; if(top==NULL) cout<<"Stack Underflow"<<endl; else { cout<<"The popped element is "<< temp->data <<endl; top = temp->next; delete (temp); } }

int main() { int ch, val; cout<<"1) Push in stack"<<endl; cout<<"2) Pop from stack"<<endl; cout<<"3) Display stack"<<endl; cout<<"4) Exit"<<endl; do { cout<<"Enter choice: "<<endl; cin>>ch; switch(ch) { case 1: cout<<"Enter value to be pushed:"<<endl; cin>>val; push(val); break; case 2: pop(); break; case 3: display(); break; case 4: cout<<"Exit"<<endl; break; default: cout<<"Invalid Choice"<<endl; } }while(ch!=4); return 0; }

StackSummary • Stack Operation Complexity Array Fixed-Size List Singly-Linked Pop() O(1) O(1) Push(o) O(1) O(1) Top() O(1) O(1) Size(), isEmpty() O(1) O(1)

Queue implementation using Linked List • Basic idea: • Create a linked list to which items would be added to one end and deleted from the other end. • Two pointers will be maintained: • One pointing to the beginning of the list (point from where elements will be deleted). • Another pointing to the end of the list (point where new elements will be inserted). 42 Front Rear DELETION INSERTION

front rear ENQUEUE front rear DEQUEUE

Algorithms –enqueue & dequeue • Algorithm enqueue (value) • Step 1 - Create a newNode with given value and set 'newNode → next' to NULL. • Step 2 - Check whether queue is Empty (rear == NULL) • Step 3 - If it is Empty then, set front = newNode and rear = newNode. • Step 4 - If it is Not Empty then, set rear → next = newNode and rear = newNode. • Algorithm dequeuer () • Step 1 - Check whether queue is Empty (front == NULL). • Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from the function • Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'. • Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).

void Delete() { temp = front; if (front == NULL) { cout<<"Underflow"<<endl; return; } else if (temp->next != NULL) { temp = temp->next; cout<<"deleted from queue is : "<<front->data; delete(front); front = temp; } else { cout<<"deleted from queue is : "<<front->data; delete(front); front = NULL; rear = NULL; } } #include <iostream> using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert() { int val; cout<<"Insert the element in queue :”; cin>>val; if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } }

int main() { int ch; cout<<"1) Insert element to queue"<<endl; cout<<"2) Delete element from queue"<<endl; cout<<"3) Display all the elements of queue"<<endl; cout<<"4) Exit"<<endl; do { cout<<"Enter your choice : "<<endl; cin>>ch; switch (ch) { case 1: Insert(); break; case 2: Delete(); break; case 3: Display(); break; case 4: cout<<"Exit"<<endl; break; default: cout<<"Invalid choice"<<endl; } } while(ch!=4); return 0; } void Display() { temp = front; if ((front == NULL) && (rear == NULL)) { cout<<"Queue is empty"<<endl; return; } cout<<"Queue elements are: "; while (temp != NULL) { cout<<temp->data<<" "; temp = temp->next; } cout<<endl; }

QueueSummary • Queue Operation Complexity Array Fixed-Size List Singly-Linked dequeue() O(1) O(1) enqueue(o) O(1) O(1) front() O(1) O(1) Size(), isEmpty() O(1) O(1)

Revisiting a data structures in detail with linked list stack and queue

More Related Content

What's hot

Similar to Revisiting a data structures in detail with linked list stack and queue

Recently uploaded

Revisiting a data structures in detail with linked list stack and queue