Circularly Linked List

Circularly linked list is a linked list where all nodes are connected to form a circle.There is no end or rear or null pointer.

Circularly Linked List

Circular linked list can be implemented in both singly linked list as well as doubly linked list.
The only difference between implementation of a circularly linked list and other linked list is that, Circularly linked list doesn't have a last element instead points to the head.Whereas other linked list points to null in place of the head.

To traverse through all the elements in the circularly linked list, we need to use two loops 

1. One which checks the condition that the head reference is not equal to null
2. Other loop which checks if the loop doesn't repeat. i.e temp variable doesn't equal to head.

Function to push an element into the Circularly linked list 

/* Function to insert a node at the begining of a Circular linked list */ void push(struct node **head_ref, int data) { struct node *ptr1 = (struct node *)malloc(sizeof(struct node)); struct node *temp = *head_ref; ptr1->data = data; ptr1->next = *head_ref; /* If linked list is not NULL then set the next of last node */ if (*head_ref != NULL) { while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; /*For the first node */ *head_ref = ptr1; }

1) Linked List is empty: a) since new_node is the only node in CLL, make a self loop. new_node->next = new_node; b) change the head pointer to point to new node. *head_ref = new_node; 2) New node is to be inserted just before the head node: (a) Find out the last node using a loop. while(current->next != *head_ref) current = current->next; (b) Change the next of last node. current->next = new_node; (c) Change next of new node to point to head. new_node->next = *head_ref; (d) change the head pointer to point to new node. *head_ref = new_node; 3) New node is to be inserted somewhere after the head: (a) Locate the node after which new node is to be inserted. while ( current->next!= *head_ref && current->next->data < new_node->data) { current = current->next; } (b) Make next of new_node as next of the located pointer new_node->next = current->next; (c) Change the next of the located pointer current->next = new_node;

Source: Geeksforgeeks
Also Refer to Tortoise-Hare Algorithm

Doubly Linked list

A doubly linked list contains an extra pointer which points to the previous element of a list and which does not exist in a singly linked list.This makes easy traversal of a linked list to the previous elements.

Algorithm for insertion 

of an element in a Doubly Linked List . Insertion can be classified into 3 different methods.

1. Insertion at the Head
2. Insertion at a given postion 
3. Insertion at the end of the Linked List 

Insertion at the head

1.Allocate a node 2. Put in the data 3.Make the next of the new node as head and previous as Null 4.Change the prev of head node to new Node. 5. Move prev of head to point to the new node

Insertion after a given position

1.Allocate a new Node 2.Put in the data 3.Make next of new node as next of prev node new_node->next=prev-node->next 4.Make the next of prev_node as new_node prev-node->next=new_node 5.Make prev-node as previous of new-node new_node->prev= prev_node 6.Change previous of new_node's next node

Insertion of a node towards the end

1.Allocate a node 2.Put in the data 3.This new node is going to be the last node, so make next of it as NULL new_node->next=NULL 4.Traverse the list to the end 5.Change the next of last node as new node 6.Make the last node as prev of new node

Algorithm for deletion of a node

1.If node to be deleted is the head node head=del_node->next 2.Check the next node only if the node to be deleted is not the last node. if(del->next != NULL) del->next->prev = del->prev; 3.Check the prev node only if the node to be deleted is not the first node. if(del->prev != NULL) del->prev->next = del->next; 4.Delete the memory

Algorithm for reversing a Doubly Linked List

/* Function to reverse a Doubly Linked List */ void reverse(struct node **head_ref) { struct node *temp = NULL; struct node *current = *head_ref; /* swap next and prev for all nodes of doubly linked list */ while (current != NULL) { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } /* Before changing head, check for the cases like empty list and list with only one node */ if(temp != NULL ) *head_ref = temp->prev; }
Source: GeeksforGeeks

Advantages over Singly Linked list

1. Can be traversed front and back from any location
2. Less ambiguity in deleting an element from the linked list.

Disadvantages over a Singly Linked list

1. Every Node takes in an extra pointer when a linked list could be created with a single pointer.
2. Extra maintenance.

Important Links to Follow
Doubly Linked List(Geeksforgeeks)
Code for doubly Linked List

Tortoise & Hare Algorithm

Tortoise & Hare algorithm is also known as Floyd's Cycle-Finding Algorithm.This is a technique for detecting infinite loops inside a linked list, symlinks, state machines etc.

To detect a loop inside a linked list
Source

• Make a pointer to start of the linked list and call it Hare 
• Make a pointer to the head of the linked list and call it Tortoise 
• advance the Hare by two and the tortoise by one for every interation.
• There's a loop if the Tortoise and Hare meet
• There's no loop if the Hare reaches the end.

Algorithm is intersting as it takes O(n) time and O(1) space.

Python code to understand Tortoise and Hare algorithms
Source

def floyd(f,x0): tortoise=f(x0) hare=f(f(x0)) while tortoise!=hare: tortoise=f(tortoise) hare=f(f(hare)) mu=0 tortoise=x0 while tortoise!=hare: tortoise=f(tortoise) hare=f(hare) mu+=1 lam=1 hare=f(tortoise) while(tortoise!=hare): hare=f(hare) lam+=1 return lam,mu


With this Algorithm we detect the loops and iterations in a circularly linked list as suggested by the name Floyd's Cycle-finding Algorithm.

More Reference: Coding Freak

Stack

Stack is a linear data structure which follows a particular order in which the operations are performed. Order is LIFO(Last In First Out) or FILO(First In Last Out)

Three main operations of a stack are :

1. Push
2. Pop
3. Peek or Top

Stack

Push

The Push Operation pushes an element into the stack.

Pop

Pop operation removes the top most element in the stack.

Peek

Peek or top operation returns the top most value of the stack.

To understand stack, you can assume a pile of books placed one over the other.To get the last book in the stack, one needs to take away all the books before the last book.

Applications of Stack

1. Recursion
2. Tower of Hanoi
3. Converting Infix to Postfix.

Stack can be implemented in two different ways: 

1. Stack Implementation using Arrays 
2. Stack Implementation using Linked list

The implemented codes are carried out into separate blogs in the above given links.

More stack related blogs

Stack Implementation Using Linked list

Implementation of a stack using linked list is dynamic and flexible. Yet the space consumed is high and adding or manipulating the linked list is complex.
Refer to the code for more details. The Code language is C++.

Code:

//Implementation of a stack using a Singly Linked List #include<iostream> using namespace std; class stack{ public: struct Node{ int data; struct Node* Link; }; struct Node* top=NULL;//initially my stack is empty void push(){ int x; struct Node* temp=new Node(); cout<<"\nEnter the data: "; cin>>x; temp->data=x; temp->Link=top; top=temp; } void pop(){ if(top==NULL){ cout<<"\nStack underflow"<<endl; }else{ top=top->Link; } } //function to peek into the stack void peek(){ cout<<"\nPeeping into the stack:"<<endl; cout<<top->data; } //function to check if the stack is empty void isEmpty(){ if(top==NULL){ cout<<"\nThe Stack is empty"<<endl; }else{ cout<<"\nThe stack is not empty"<<endl; } } //function to print the elements of the stack void print(){ Node* temp=new Node(); temp=top; cout<<"Printing Elements in a stack"<<endl; while(temp!=NULL){ cout<<temp->data<<endl; temp=temp->Link; } } void sizeofstack(){ Node* temp=new Node(); temp=top; int sizeoftemp; while(temp!=NULL){ temp=temp->Link; sizeoftemp+=sizeof(temp); } cout<<"\nSize of the stack"<<sizeoftemp<<endl; } //function to choose the stack operations void option(){ int x=1; int options; while(x!=0){ cout<<"\nStack operations:"<<endl; cout<<"1.Push"<<endl; cout<<"2.Pop"<<endl; cout<<"3.Peek"<<endl; cout<<"4.Is Empty?"<<endl; cout<<"5.Print Stack"<<endl; cout<<"6.Stack Size"<<endl; cout<<"7.Exit"<<endl; cout<<"Enter option"<<endl; cin>>options; switch(options){ case 1: push(); break; case 2: pop(); break; case 3: peek(); break; case 4: isEmpty(); break; case 5: print(); break; case 6: sizeofstack(); break; case 7: exit(0); break; } } } }; int main(){ stack k; k.option(); }

Output:

Stack Implementation Using Array

This blog will deal with implementation of stack using arrays.The implementation is simple yet we need to allocate a pre-defined size.The allocated size may or may not be utilized completely. This makes the array implementation non-flexible.

Using Array

#include<stdio.h> #include<stdlib.h> #define MAX_SIZE 101 int A[MAX_SIZE]; int top=-1; void Push(int x){ if(top==MAX_SIZE-1){ printf("Error;stack overflow\n"); } A[++top]=x; } void pop(){ if(top==MAX_SIZE-1){ printf("Error: No element to pop\n"); } top--; } int Top(){ return A[top]; } void print(){ int i; printf("Stack :"); for(i=0;i<=top;i++){ printf("\n%d",A[i]); } printf("\n"); } int main(){ Push(2); print(); Push(10); print(); pop(); Top(); Push(7); print(); pop(); }



Output

---

Linked List v/s Arrays

Linked list is a replacement to the arrays. Since arrays take in a block of memory so the flexibility is very less.It has a defined structure which uses a limited memory and uses only when the memory is required. Though adding more elements is a cumbersome task.

Each node in a list consists of at least two parts:

1. Data
2. Pointer to the next node

struct Node{ int data; Node* next; }

A tabular comparison of Arrays v/s Linked List:

S. No	Parameter		Arrays	Linked list
1	Cost		Constant time O(1)	O(n)
2	Memory usage		Fixed Size Contiguous Blocks of memory	No unused memory, Extra memory for pointer variables
3	Cost of inserting and Deleting elements	At the beginning	O(n) Shifting one index at a time to the right	Creating a new node and head pointer O(1)
		At the end	If Array not full O(1) else O(n)	Traversing a new node & End
		At the nth position	O(n)	O(n)
4	Ease of Use		Very Easy	Complicated especially in C/C++

Advantages over arrays

1. Dynamic size
2. Ease of insertion/deletion

Drawbacks:

1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2. Extra memory space for a pointer is required with each element of the list.

Linked List

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference  to the next node in the sequence.

                                   

Types of Linked List: 

Based on the working of a data structure, we list only a few important linked list models.

1. Singly Linked list
2. Doubly Linked list 
3. Circular Linked list

Others forms of linked lists include multiply linked list, sentinal nodes etc.

Advantages

• Linked lists are a dynamic data structure, allocating the needed memory while the program is running.
• Insertion and deletion node operations are easily implemented in a linked list.
• Linear data structures such as stacks and queues are easily executed with a linked list.
• They can reduce access time and may expand in real time without memory overhead.

Disadvantages

• They have a tendency to use more memory due to pointers requiring extra storage space.
• Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
• Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
• Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer.

Abstract Data Types(ADT)

An abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

ADT is a theoretical concept in computer science, used in the design and analysis of algorithms, data structures, and software systems, and do not correspond to specific features of any computer languages.

In ADTs,inferences are derived using a mathematical or a logical module.It is very much equivalent to writing a set of points understandable to a user.Lets assume a list with user input data which can be implemented in two ways:

1. Using Arrays
2. Using Linked Lists

Both have their own set of advantages and disadvantages,But it is made sure that advantages are used to make our understanding ends meet and the idea to implement looks concrete.

Each data structure has its limitations. One such data structure is a Linked list which is followed in the next chapter.