You cannot copy content of this page.

Sep 30,2012
Leave a comment
By admin

**Singly Linked List**

**Creation of a Singly Linked List (LIFO, FIFO, Sorted)**

Creation of a linked list may be in any order say LIFO, FIFO or Sorted. If a linked list is created considering LIFO order, then insertions as well as deletions are done at the same end i.e. the last node of the linked list is the first one to be deleted. If a linked list is created considering FIFO order, then insertions are done one end, whereas deletions are performed at the other end. Thus, the first node to be deleted is only that node which is inserted first in the linked list. However, creating a Sorted Linked List involves insertion of a new node in the linked list such that the order of the list is preserved. The order to be retained in the list may be chosen as either ascending or descending order.

**Representation of a Linked List: **

A singly linked list is one in which one node points to the next node and so on, where node contains an information part and an address to the next node of the same type. The concept of linked list may be illustrated using the following figure:

A singly linked list is uni-directional. That is, the first node points to the next node, but the next node does not contain the address of the previous node. Thus such lists can be easily traversed and operated upon from left to right i.e in one direction. Though, manipulations to the above may result in the other way traversal also, which is discussed in further sections.

A linked list is represented by a structure in ‘C’, which is generally composed of two parts, first part is the information part and the other part is the address of the next node pointed to be the previous node. Thus such a structure results in a self-referential structure. The structure definition is as follows:

struct list

{int info;

struct list *next;

};

struct list *head=NULL;

A global variable head is declared, which is considered to be the first node of the linked list. However, you may also declare head as a local variable to main function, but that requires passing head as an argument to each function for operating upon the linked list and returning the same from within the function, whereas, global definition avoids this condition of passing head as an argument and returning head pointer.

**In-order traversal:** The function for traversing a linked list in In-order way is as follows:

/*In-order traversal*/

void displaylist(list *head)

{

list *temp;

if(head==NULL)

{printf(“nList is empty.”);

return;

}

temp=head;

while(temp!=NULL)

{printf(“%d->”,temp->n);

temp=temp->next;

}

printf(“bb “);

}

**Reverse-order traversal:** For reading a linked list in reverse order, we can use any of the methods, such as reading last element in first scan, second last element in second scan, where number of scans is equal to the total number of elements in the linked list or by maintaining an array of pointers that point to each node of the linked list and using this array of pointers read the linked list in reverse order.

The function for traversing/ reading a linked list in reverse order is as follows:

**/*Reverse order traversal*/**

void displaylistreverse(list *head)

{

list *temp;

int i,j,count=0;

if(head==NULL)

{printf(“nList is empty.”);

return;

}

for(temp=head;temp!=NULL;temp=temp->next,count++);

for(i=1;i<=count;i++)

{temp=head;

for(j=1;j<=count-i;j++)

{temp=temp->next;

}

printf(“%d->”,temp->n);

}

printf(“bb “);

}

**Unsorted search:** Search is the process of searching an element in a given linked list. Search process may be sorted as well as unsorted. Unsorted search means search is performed in a linked list containing elements that are not sorted. Thus sorting operation must be performed for n nodes of a linked list.

The ‘C’ function for unsorted search is as follows:

/*UnSorted search on an unsorted list*/

void unsortedsearch(list *head,int val)

{

list *temp;

if(head==NULL)

{printf(“nList is empty.”);

return;

}

temp=head;

/*searches for equality until number is found*/

/*best case is when first number is the required number*/

/*worst case is number does not exist*/

/*or number is present at last position in list*/

while(temp!=NULL)

{if(temp->n==val)

{printf(“nNumber found.”);

return;

}

temp=temp->next;

}

printf(“nNumber not found.”);

}

**Sorted search: **In case of sorted search, there are two cases. If the linked list is sorted in ascending order, as soon as the number to be searched becomes smaller than the element in the linked list, search process terminates without resuming upto n elements. On the other hand, if the linked list is sorted in descending order, then while scanning from the first element onwards, as soon as the number to be searched becomes greater than the element in the linked list, the search process terminates. Thus efficiency of a sorted search is higher as compared to that of unsorted search for a given set of numbers.

The function to perform sorted search is as follows:

/*Sorted search on a list sorted in ascending order*/

void sortedsearch(list *head,int val)

{

list *temp;

if(head==NULL)

{printf(“List is empty.”);

return;

}

temp=head;

while((temp->n!=val) && (val>temp->n) && (temp!=NULL))

temp=temp->next;

if(temp->n==val)

printf(“nNumber found.”);

else

printf(“nNumber not found.”);

}

- Beginning
- End
- After given element/node
- Before given element/node

**Insertion at Beginning:** The ‘C’ function is as follows:

/*Insertion at beginning*/

list *insertbegin(list *head,int x)

{

list *temp,*ptr=makenode(x);

if(head==NULL)

{head=ptr;

}

else

{ptr->next=head;

head=ptr;

}

return head;

}

**Insertion at End:** For inserting an element at the end of the linked list, we must take a temp pointer that points to the head node (first node of the linked list) and moves forwards until the next node of temp becomes NULL. After temp pointer is positioned at the last element, new node may be inserted by setting appropriate pointers as follows:

/*Insertion at end*/

list *insertend(list *head,int x)

{

list *temp,*ptr=makenode(x);

if(head==NULL)

{head=ptr;

}

else

{temp=head;

while(temp->next!=NULL)

temp=temp->next;

temp->next=ptr;

}

return head;

}

**Insertion after given node:** For inserting an element after a given node, we must search that element in the list. If that element is not found, error is reported, otherwise the new element is inserted after the searched element by setting pointers which are shown in the following function:

/*Insertion after given element/node*/

list *insertafternode(list *head,int x,int node)

{

list *temp,*ptr=makenode(x);

if(head==NULL)

{printf(“nGiven node does not exist. List empty”);

}

else

{temp=head;

while(temp->n!=node)

temp=temp->next;

if(temp==NULL)

{printf(“nGiven node not found in list.”);

}

else

{ptr->next=temp->next;

temp->next=ptr;

}

}

return head;

}

**Insertion before given node:** If you wish to insert a new node before a given node, then locate the node before which you wish to insert and maintain the address of its previous node. Once this is done, this case becomes similar to that of insertion after a given node, by considering the pointer to the previous node of the searched node. The ‘C’ function is as follows:

/*Insertion before given element/node*/

list *insertbeforenode(list *head,int x,int node)

{

list *temp,*ptr=makenode(x);

if(head==NULL)

{printf(“nGiven node does not exist. List empty”);

}

else

{if(head->n==node)

{ptr->next=head;

head=ptr;

return head;

}

else

{temp=head;

while(temp->next->n!=node)

temp=temp->next;

if(temp==NULL)

{printf(“nGiven node not found in list.”);

}

else

{ptr->next=temp->next;

temp->next=ptr;

}

}

}

return head;

}

- Beginning
- End
- After given element/node
- Before given element/node

/*function to delete first node*/

list *delfirstnode(list *head)

{list *temp;

if(head==NULL)

{printf(“nList is empty!”);

return head;

}

temp=head;

head=head->next;

free(temp);

return head;

}

/*function to delete last node*/

list *dellastnode(list *head)

{list *ptr,*temp;

if(head==NULL)

{printf(“nList is empty!”);

return head;

}

if(head->next==NULL)

{temp=head;

head=NULL;

free(temp);

return head;

}

temp=head;

if(temp->next->next==NULL)

{ptr=temp->next;

temp->next=NULL;

free(ptr);

return head;

}

while(temp->next->next!=NULL)

temp=temp->next;

ptr=temp->next;

temp->next=ptr->next;

free(ptr);

return head;

}

**Deletion after a given node:** To delete a node after a given node, input the node after which you wish to delete. Then, locate that node in the linked list. If that node is not found in the list, report an error, otherwise place a pointer temp on that node. Perform deletion of the next node by setting appropriate pointers.

/*function to delete node after a given node*/

list *delafternode(list *head,int node)

{

list *temp,*ptr;

if(head==NULL)

{printf(“nList is empty.”);

return head;

}

/*locate given node in the list*/

for(temp=head;((temp->n!=node) && (temp!=NULL));temp=temp->next);

if(temp==NULL)

{printf(“nGiven node does not exist in the list.”);

return head;

}

ptr=temp->next;

temp->next=ptr->next;

free(ptr);

return head;

}

**Deletion before a given node: ** To delete a node before a given node, input the node before which you wish to delete. Locate that node in the list and place two pointers, one on the node before given node and other before the node to be deleted. Then perform necessary pointer adjustments for deleting the node before the given node as follows:

/*function to delete node before a given node*/

list *delbeforenode(list *head,int node)

{

list *temp,*temp1,*ptr;

if(head==NULL)

{printf(“nList is empty.”);

return head;

}

if(head->n==node)

{printf(“nCannot delete before first node.”);

return head;

}

/*locate given node in the list*/

temp=head;

while((temp->next->n!=node) && (temp!=NULL))

{temp1=temp;

temp=temp->next;

}

if(temp==NULL)

{printf(“nGiven node does not exist in the list.”);

return head;

}

ptr=temp1->next;

temp1->next=ptr->next;

free(ptr);

return head;

}

/*Reversing list*/

list *reverselist(list *head)

{

list *temp,*head1=NULL,*ptr,*temp1;

int i,j,count=0;

if(head==NULL)

{printf(“nList is empty.”);

return head;

}

for(temp=head;temp!=NULL;temp=temp->next,count++);

for(i=1;i<=count;i++)

{temp=head;

for(j=1;j<=count-i;j++)

{temp=temp->next;

}

printf(“%d->”,temp->n);

ptr=(list *)malloc(sizeof(list));

ptr->n=temp->n;

ptr->next=NULL;

if(head1==NULL)

{head1=ptr;

}

else

{temp1=head1;

while(temp1->next!=NULL)

temp1=temp1->next;

temp1->next=ptr;

}

}

printf(“bb “);

temp=head;

while(temp!=NULL)

{ptr=temp;

temp=temp->next;

free(ptr);

}

return head1;

}

**Disposing list:** Disposing a linked list means removing all the elements of the linked list. The function is as follows:

/*Disposing linked list*/

list *dispose(list *head)

{

list *ptr,*temp;

printf(“nDisposing the linked list.”);

printf(“nPress any key to continue…”);

while(head!=NULL)

{temp=head;

head=head->next;

free(temp);

}

return head;

}

**Concatenation:** The concatenation operation results in combining two lists such that the second list is attached at the last nodal point of the first list. The ‘C’ function for concatenation is as follows:

/*Concatenating list*/

list *concatenate(list *head1,list *head2)

{

list *temp=head1;

while(temp->next!=NULL)

temp=temp->next;

temp->next=head2;

return head1;

}

- Middle
- Alternate nodes
- After/Before given node

**Splitting at middle: **The splitting at middle involves dividing a given linked list into two equal parts. However, if the odd number of nodes are present in the list, then it is splitted from the node which is achieved by dividing the size of the list by 2. The ‘C’ function to split the node from the middle is as follows:

/*Splitting from middle*/

void splitmiddle(list *head)

{

list *head1=NULL,*temp;

int i,count=0;

for(temp=head;temp!=NULL;temp=temp->next)

count++;

temp=head;

/*i is 1 since temp is already at first node*/

for(i=1;i<count/2;i++)

temp=temp->next;

head1=temp->next;

temp->next=NULL;

printf(“nSplitting list task over.”);

printf(“nDisplaying first list:”);

for(temp=head;temp!=NULL;temp=temp->next)

printf(“%d->”,temp->n);

printf(“bb “);

printf(“nDisplaying second list:”);

for(temp=head1;temp!=NULL;temp=temp->next)

printf(“%d->”,temp->n);

printf(“bb “);

}

**Splitting alternate nodes:** The split operation at alternate nodes results in creating two lists – an odd list and an even list. The odd list contains nodes at position 1, 3, 5 and so on, whereas an even list contains nodes at position 2, 4, 6 and so on. The ‘C’ function to split a given linked list at alternate nodes is as follows:

/*Splitting alternate nodes*/

void splitalternatenodes(list *head)

{

list *head1=NULL,*head2=NULL,*temp,*temp1,*ptr;

int i;

for(i=1,temp=head;temp!=NULL;temp=temp->next,i++)

{

ptr=(list *)malloc(sizeof(list));

ptr->n=temp->n;

ptr->next=NULL;

/*creating odd list*/

if(i%2!=0)

{if(head1==NULL)

head1=ptr;

else

{temp1=head1;

while(temp1->next!=NULL)

temp1=temp1->next;

temp1->next=ptr;

}

}

else /*creating even list*/

{if(head2==NULL)

head2=ptr;

else

{temp1=head2;

while(temp1->next!=NULL)

temp1=temp1->next;

temp1->next=ptr;

}

}

}

printf(“nAlternate node Splitting list task over.”);

printf(“nDisplaying first list:”);

for(temp=head1;temp!=NULL;temp=temp->next)

printf(“%d->”,temp->n);

printf(“bb “);

printf(“nDisplaying second list:”);

for(temp=head2;temp!=NULL;temp=temp->next)

printf(“%d->”,temp->n);

printf(“bb “);

}

**Splitting after given element/node:** The node after which the deletion operation is to be performed is taken as an input from the user. This node is located in the linked list. The node next to located node, if it exists, is removed by appropriate pointer adjustments. If the given node does not exist in the list, an error is flashed. The ‘C’ function is as follows:

/*Splitting after a given node*/

void splitafternode(list *head,int node)

{list *temp,*head1=NULL;

temp=head;

while((temp!=NULL)&&(temp->n!=node))

{temp=temp->next;

}

if(temp==NULL)

{printf(“nGiven node does not exist.”);

return;

}

if(temp->n==node)

{head1=temp->next;

temp->next=NULL;

}

printf(“nSplit task after given node is over.”);

printf(“nDisplaying first list:”);

for(temp=head;temp!=NULL;temp=temp->next)

printf(“%d->”,temp->n);

printf(“bb “);

printf(“nDisplaying second list:”);

for(temp=head1;temp!=NULL;temp=temp->next)

printf(“%d->”,temp->n);

printf(“bb “);

}

**Splitting before given element/node:** The node before which deletion is to be performed is taken as an input. Then the next node from head is searched for this node. Two pointers one on previous to given node and other to previous to previous is maintained. If the node is found, then deletion is performed by setting pointers appropriately and freeing the memory for the deleted node. The ‘C’ function is as follows:

/*Split before given node*/

void splitbeforenode(list *head,int node)

{list *temp,*head1=NULL;

temp=head;

/*if there is only one node*/

if(temp->n==node)

{head1=temp;

head=NULL;

}

else

{

while((temp!=NULL)&&(temp->next->n!=node))

{temp=temp->next;

}

if(temp==NULL)

{printf(“nGiven node does not exist.”);

return;

}

if(temp->next->n==node)

{head1=temp->next;

temp->next=NULL;

}

}

printf(“nSplit task before given node is over.”);

printf(“nDisplaying first list:”);

for(temp=head;temp!=NULL;temp=temp->next)

printf(“%d->”,temp->n);

printf(“bb “);

printf(“nDisplaying second list:”);

for(temp=head1;temp!=NULL;temp=temp->next)

printf(“%d->”,temp->n);

printf(“bb “);

}

**Merging: **Merging two sorted lists is the process of combining two lists such that the resultant list is also sorted. For example: consider list one as {1,3,5,7} and list two as {2,4,6,8}. Then merging of both these lists result in a third list that contains the following elements: {1,2,3,4,5,6,7,8}. The ‘C’ function to perform merging is given below:

list *merge(list *head1,list *head2)

{list *head=NULL,*temp1,*temp2,*ptr,*tmp;

temp1=head1;

temp2=head2;

while((temp1!=NULL)&&(temp2!=NULL))

{if(temp1->n<temp2->n)

{

ptr=(list *)malloc(sizeof(list));

ptr->n=temp1->n;

ptr->next=NULL;

if(head==NULL)

head=ptr;

else

{tmp=head;

while(tmp->next!=NULL)

tmp=tmp->next;

tmp->next=ptr;

}

temp1=temp1->next;

}

else

{

ptr=(list *)malloc(sizeof(list));

ptr->n=temp2->n;

ptr->next=NULL;

if(head==NULL)

head=ptr;

else

{tmp=head;

while(tmp->next!=NULL)

tmp=tmp->next;

tmp->next=ptr;

}

temp2=temp2->next;

}

}

while(temp1!=NULL)

{

ptr=(list *)malloc(sizeof(list));

ptr->n=temp1->n;

ptr->next=NULL;

if(head==NULL)

head=ptr;

else

{tmp=head;

while(tmp->next!=NULL)

tmp=tmp->next;

tmp->next=ptr;

}

temp1=temp1->next;

}

while(temp2!=NULL)

{

ptr=(list *)malloc(sizeof(list));

ptr->n=temp2->n;

ptr->next=NULL;

if(head==NULL)

head=ptr;

else

{tmp=head;

while(tmp->next!=NULL)

tmp=tmp->next;

tmp->next=ptr;

}

temp2=temp2->next;

}

return head;

}

**Program for operations on a Singly Linked List**

Stack is a Last In First Out linear data structure. It can be implemented using structures. An example to illustrate how Stacks can be implemented using structures is given below:

/*Program to implement Stack using structures*/

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define MAX 10

struct stack{

int top;

int arr[MAX];

};

/*Push to insert an element at the top of the stack */

void push(struct stack *, int);

/* Pop to return the top-most element of the stack */

int pop(struct stack *);

/* Display the contents of stack */

void display(struct stack *);

int main(){

/* stack object created */

struct stack s;

int ch, num;

s.top = -1;

while(1){

printf(“nStack-Menu”);

printf(“n1. Pushn2. Popn3. Displayn4. Exit”);

printf(“nEnter your choice?”);

scanf(“%d”,&ch);

switch(ch){

case 1:

printf(“Enter number to push?”);

scanf(“%d”,&num);

push(&s,num);

break;

case 2:

num = pop(&s);

printf(“Popped element = %d”,num);

break;

case 3:

display(&s);

break;

case 4:

exit(0);

default:

printf(“Invalid choice!”);

}

getch();

}

}

/* stack object created */

struct stack s;

int ch, num;

s.top = -1;

while(1){

printf(“nStack-Menu”);

printf(“n1. Pushn2. Popn3. Displayn4. Exit”);

printf(“nEnter your choice?”);

scanf(“%d”,&ch);

switch(ch){

case 1:

printf(“Enter number to push?”);

scanf(“%d”,&num);

push(&s,num);

break;

case 2:

num = pop(&s);

printf(“Popped element = %d”,num);

break;

case 3:

display(&s);

break;

case 4:

exit(0);

default:

printf(“Invalid choice!”);

}

getch();

}

}

void push(struct stack *s, int x){

if(s->top==MAX-1){

printf(“Stack full! Overflow.”);

return;

}

s->arr[++(s->top)]=x;

}

int pop(struct stack *s){

if(s->top==-1){

printf(“Stack empty! Underflow.”);

return -1;

}

return(s->arr[s->top–]);

}

void display(struct stack *s){

int t;

if(s->top==-1){

printf(“Stack empty!”);

return;

}

/*assigning top to another variable*/

for(t=s->top;t>=0;t–)

printf(“%dt”,s->arr[t]);

}

- Stacks
- Introduction
- Representation
- Operations
- Implementation
- Representing two stacks in an array
- Application of stacks
- Parenthesis checker
- Evaluation of Postfix expression
- Evaluation of Prefix expression
- Evaluation of Infix expression
- Conversion from Infix to Postfix
- Conversion from Infix to Prefix
- Conversion from Postfix to Prefix
- Conversion from Postfix to Infix
- Conversion from Prefix to Postfix
- Conversion from Prefix to Infix

- Recursion

A stack is a linear data structure, which can be operated upon at only one end, which is generally referred to as the top of the stack. An example to illustrate stack arrangement is keeping a bunch of files in a drawer, which can only be inserted at the top as well as removed from the top. For this reason, stack is called a LIFO structure i.e. Last In First Out.

The basic operations that may be performed on stacks are push and pop operations. Push operation refers to putting an element on the top of the stack, whereas pop operation removes the topmost element from the stack. Stacks are required in situations where data must be stored and then processed in reverse order. Stack is an abstract data structure.

Example: Push 5, 6, 7 will be represented in fig (i), (ii) & (iii).

In the above figures, the downward pointing arrow refers to top that points to the topmost element of the stack.

Pop will be in LIFO order {7,6,5} as shown in fig. (i), (ii) & (iii).

The upward pointing arrow indicates element at the top of the stack, which is removed in the order (7,6,5) as shown above.

A stack may be represented using arrays and by keeping an integer variable ‘top’ that points to the topmost element of the stack. Simply stating, stack may be represented using structures, which is composed of an array of elements and top that refers to the topmost element of the stack. A stack may also be represented using a linked list. One end of the stack is considered to be fixed which is the bottom of the stack and top shifts as elements are pushed and popped. Thus stack may be represented as follows:

struct stack{

int top;

int arr[MAX];

};

The object of the structure stack may be instantiated as follows:

struct stack s;

**Outline of Syllabus**

- Basic concepts of Data Representation
- Introduction to Algorithm Design
- Arrays
- Linked List
- Stacks
- Queues
- Trees
- Searching, Sorting and Hashing
- Graphs

**Detailed Contents**

- Linear arrays
- Memory representation/address calculation
- Operations
- Traversal
- Search
- Insertion
- Deletion

- Two Dimensional arrays

- Stacks
- Introduction
- Representation
- Operations
- Implementation
- Representing two stacks in an array
- Application of stacks
- Parenthesis checker
- Evaluation of Postfix expression
- Evaluation of Prefix expression
- Evaluation of Infix expression
- Conversion from Infix to Postfix
- Conversion from Infix to Prefix
- Conversion from Postfix to Prefix
- Conversion from Postfix to Infix
- Conversion from Prefix to Postfix
- Conversion from Prefix to Infix

- Recursion

- Trees
- Introduction
- Terminology
- Binary Trees
- Binary Search Trees
- Threaded Binary Trees
- Representation
- Creation
- Insertion
- In-order traversal
- Deletion
- Disposing

- Advanced Trees

- Searching, sorting and hashing
- Linear & Binary Search
- Sorting
- Insertion sort
- Selection sort (General and Straight)
- Quick sort
- Merge sort
- Heap sort
- Radix sort
- Bubble sort
- Shell sort
- Linear sort
- Address calculation sort
- Sorting on multiple keys

- Indexed Search
- Hash Tables and Hashing
- Direct Address tables
- Hash functions
- Division
- Prime division
- Folding
- Mid-square
- Multiplication
- Radix transformation
- Digit re-arrangement

- Hash tables
- Initializing
- Inserting
- Deleting
- Searching

- Resolving collisions
- Chaining
- Direct
- Coalesced

- Open addressing
- Linear probing
- Quadratic probing

- Rehashing

- Chaining

- Graphs
- Representation
- Traversal schemes
- Minimal Spanning