Data Structures

chapter 1


 

Data :

Factual information in a form that can be input to, created by, processed by, stored in, and output by a computer. Data can take the form of characters such as letters, numbers, punctuation marks, mathematical operators, and control characters.

Information

is valuable because it can affect behavior, a decision, or an outcome.

is the summarization of data. Technically, data are raw facts and figures that are processed into information, such as summaries and totals.

052814_DATA-v.-INFO_tricolor-08

FUNDAMENTAL OF DATA STRUCTURES

Linear [elements are in series]   |   Non Linear [elements not in series]

     Array                                                                                           Tree

         Queue                                                                                           Graph

       Stack                                                                                               Table

     Link list                                                                                        Sets

 

IT_Officer_039_01

 

ARRAY

In programming, a series of objects all of which are the same size and type. Each object in an array is called an array element. For example, you could have an array of integers or an array of characters or anarray of anything that has a defined data type.

clip_image00213

arrayname[0] = "This ";
arrayname[1] = "is ";
arrayname[2] = "pretty simple.";

print arrayname[0];
print arrayname[1];
print arrayname[2];

 

QUEUE

A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle.

Types of data structure2

A queue is an example of a linear data structure, or more abstractly a sequential collection. Queues provide services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later.

STACK

The stack is a common data structure for representing things that need to maintained in a particular order. For instance, when a function calls another function, which in turn calls a third function, it’s important that the third function return back to the second function rather than the first.

632px-CPT-ADT-stacks-real-life.svg

example :  Books , Plates , no of bikes in room, hard disk inner plates .

stack-of-books-images-di7j6RneT

 

 

 

 

 

Link List :

A linked list is a finite sequence of nodes each of which contains a pointer field pointing to the next node. example : qlue game 

Link list has 2 conditions : under flow    and    over flow 

In under flow case , you target that type of link list in which there  is no data.

example :   start —–> null  [in this case there is no data]

In overflow case , if you want to enter new node in link-list and there is no free space available .

Link list has 4 operations :

insertions inserting an element at the front of the list

deletions deleting an item from the front of the list

 Searching –  searching in list

returning – the head of the list

 

Traversal  / Returning :

if the start is null  / or if the start points null , so the condition will be   Underflow .

but according to below diagram ,  if the start points / or has some data  then go to the first node  and take variable (count =0)  , than count = 0 + 1 +1 +1 +1 = 4
start —>image001

 

 

Searching –  searching in list :  

if the data “B” is available , then find its  number or  positioning . first take location variable . if “B” is not available in first then add increment of 1. now the data is available in next column so add 1 . then the location will be (2) of  “B”.

loc = 0 +1+1  =2

Stack and link list are both are data structures.

  • Stack is liner type data structure, i.e. they are arranging in liner manner.  In stack whatever is stored first it comes out last. It works in LIFO manner(Last in first out). In stack you can’t add element in between. They are like a stack of coins, i.e. if you want to take the last coin, then all the upper coins have to be removed one by one.

 

  • Link list is not a liner data structure. Here you can access any element or add any element in between. There is no LIFO of LILO manner (last in last out). In Link list you basically use to pointers , one to store the value of the variable and other to store the address of the next node(link list single element  known as node).As the next link list address is store in the second node, there is no restriction in adding a new link list element in between .  Use:
  • Linked lists provide very fast insertion or deletion of a list member. As each linked list contains a pointer to the next member in the list. Whereas there is disadvantage if you want to perform random accesses it has to go through all the lists.

DataStructuresLinkedListofN

Difference between Stack and Queue :

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

jLlQzTypes of data structure2

 

TREE

In computer science, a tree is a widely used abstract data type (ADT)–or data structure implementing this ADT–that simulates a hierarchical tree structure, with a root value and sub-trees of children with a parent node, represented as a set of linked nodes.

 2trree

 

GRAPH

In fact there are only two, nodes and edges. A node (or vertex) is a discrete position in thegraph. An edge (or connection) is a link between two vertices that can be either directed or undirected and may have a cost associated with it.

graph-12                  dg-graphs04

 

Operations of Data Structures :

Transversing   – Insertions   – Deletion   – Searching   – Merging  – Sorting

Transversing : is a operation of to visit each element exactly once , It is a generic operation .

Insertion : to store value .

Searching :  is a method to find value .

Types of searching :      Linear Search | Binary Search

Linear Search :

  • is also called sequential search.
  • is a method for finding a particular value in a list that checks each element in sequence until the desired element is found or the list is exhausted. The list need not be ordered.
  • check all values .

 

 

Program for linear search: 

#include<iostream>
#include<conio.h>
using namespace std;

int main()
{
int arr[100];
int num,tosearch ,i;

cout<<“Enter no of elements :”;
cin>>num;

cout<<“Enter no :”;

for(i=1;i<=num;i++)
{
cin>>arr[i];
}

cout<<“No to search :”;
cin>>tosearch;

for( i=1;i<=num;i++)
{
if(arr[i]==tosearch)
{
cout<<tosearch<<“is present in location”<<i;
break;
}

}
if(i==num)
{
cout<<“Error – number not found.”<<tosearch;
}

return 0;
}

 

 

Binary Search :

  • a binary search or half-interval search algorithm
  • finds the position of a target value within a sorted array / sorted form.
  • ascending order.
  1.  first it breaks the value .and find mid point .
  2.   (First value + Last value ) /2
  3. (0+4) / 2
  4. if the value is greater , than the middle value change .
  5. start = middle + 1
  6. 3+1 =4
  7. mid = 4+5/2
  8.            =4.5
  9.          4+1=5

2 34

 

5

 

 

 

67

 

 

 

binary search.PNG

 

 

 

C++ Program for Binary Searching :
#include<iostream>
#include<conio.h>
using namespace std;

int main()
{
int a[100];
int n,i,beg,ed,mid,item;

cout<<“Enter no of elements :”;
cin>>n;

cout<<“Enter sorted elements \n:”;
for(i=1;i<=n;i++)
{
cin>>a[i];
}

cout<<“Enter search element:”;
cin>>item;

beg=1;
ed=n;

mid=(beg+ed)/2;

while(beg<=ed&& a[mid]!=item)
{
if(a[mid]<item)
beg=mid+1;
else
ed=mid-1;

mid=(mid+ed)/2;
}
if(a[mid]==item)
{
cout<<“element has been found”<<mid;
}
else
cout<<“element not found”;
return 0;
}

 

 

Recursion :

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.

Recursion is solving a problem with a function that calls itself. A good example of this is a factorial function. Factorial is a math problem where factorial of 5, for example, is 5 * 4 * 3 * 2 * 1.

 

#include <iostream>
using namespace std;

int factorial(int);

int main() {
    int n;
    cout<<"Enter a number to find factorial: ";
    cin>>n;
    cout<<"Factorial of "<<n<<" = "<<factorial(n);
    return 0;
}

int factorial(int n) {
    if (n>1) {
        return n*factorial(n-1);
    }
    else {
        return 1;
    }
}


Chapter 2:      PRELIMINARIES  / INTRODUCTORY


 

Ceiling :  nearest integers upper value .  floor :  nearest integers lower value .  

Permutation :  A permutation is an arrangement of objects in specific order. The order of the arrangement is important!   or   it is a way, especially one of several possible variations, in which a set or number of things can be ordered or arranged.

 

C++ Program Permutations :

#include<iostream>
using namespace std;

/* Function to swap two characters */
void swap(char& a, char& b)
{
char temp;
temp = a;
a = b;
b = temp;
}

/* Function to obtain permutations of string characters */
void permutation(string s,int i,int n)
{
int j;
if (i == n)
cout << s << “\t”;
else
{
for (j = i; j < s.length(); j++)
{
swap(s[i],s[j]);
permutation(s, i + 1, n);
swap(s[i],s[j]);
}
}
}

int main()
{
string s;
cout << “Enter the string : “;
cin >> s;
cout << endl << “The permutations of the given string : ” << endl;
permutation(s, 0, s.length() – 1);
cout << endl;
}

Recursion : Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.  or  providing you a solution dividing in small instance.

Arithmetic / Modulus : 


—————–Control Statement —————

A control structure is a block of programming that analyzes variables and chooses a direction in which to go based on given parameters. The term flow control details the direction the program takes (which way program control “flows”).   or  A method which can specify  on basis of conditions and variable .

Types of Control statements

  1. The selection / conditional structure tests a condition, then executes one sequence of statements instead of another, depending on whether the condition is true or false. A condition is any variable or expression that returns a Boolean value (TRUE or FALSE)  : like ( if ,    else if ,    if then else , nested if else )  .
  2. The iteration /repetitive structure executes a sequence of statements repeatedly as long as a condition holds true.
  3. The sequence structure simply executes a sequence of statements in the order in which they occur. “statements run one after an other “.

 

ALGORITHM : is process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

Sub Algorithm :  is an independent component of an algorithm and for this reason is defined separately from the main algorithm. The purpose of a sub algorithm is to perform some computation when required, under control of the main algorithm. 

             Function sub algorithm        |     Procedure sub algorithm

           Function sub algorithm :  which only return single value to the main algorithm is called function sub algorithm .

            Procedure sub algorithm :  which return more than one value called the procedure sub algorithm .


Chapter 3:      STRING


string is a finite sequence of characters.

Operation of string :  sub-string   ,  index  ,  length  ,  concentration .

Substring : is  also a string , this is a sub point of string or substring .

Index : is a position where the first value of pattern will be match . 

-Length : The number of characters in string .

-Concatenation : Combination of 2 or more strings and generate new string .     example:                               S        =         SI           +         S2                                                                                                                                                           string 1            string 2

sub string : when we find  or calculate sub string ,we need 3 string .                                            w (string_name) , k (position_defined) , L (length of substring  / no of characters) .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Data Structure Spring [2014] 

Q1 :What is a use of data structure ? Explain Data Structure operations with examples ?

Data structure, in simplest terms, is data organization for its efficient use. Data structures can be of various types, depending on the application. For example, databases use different data structures than compilers.

Uses  :

  • Data structures allow information storage on hard disks.
  • provides means for management of large dataset such as databases or internet indexing services.
  • Are necessary for design of efficient algorithms.
  • allows safe storage of information on a computer. The information is then available for later use and can be used by multiple programs. Additionally, the information is secures and can not be lost (especially if it is stored on magnetic tapes).
  • allows the data use and processing on a software system.
  • Allows easier processing of data.
  • Using internet, we can access the data anytime from any connected machine (computer, laptop, tablet, phone, etc.)

Disadvantages:

  • Only advanced users can make changes to data structures
  • Any problem involving data structure will need an expert’s help, i.e. basic users can not help themselves.

 

Data Structure operations:

Following operations can be performed on the data structures:

  • Traversing
  • Searching
  • Inserting
  • Deleting
  • Sorting
  • Merging
  1. Traversing– It is used to access each data item exactly once so that it can be processed.

  2. Searching– It is used to find out the location of the data item if it exists in the given collection of data items.

  3. Inserting– It is used to add a new data item in the given collection of data items.

  4. Deleting– It is used to delete an existing data item from the given collection of data items.

  5. Sorting– It is used to arrange the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

  6. Merging– It is used to combine the data items of two sorted files into single file in the sorted form.


Q 2 :Explain procedure, algorithm, and floor ,ceiling, factorial function?

PROCEDURE : A procedure is a section of a program that performs a specific task.

ALGORITHM : A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

Floor Function  & Ceiling Function:

The greatest integer that is less than (or equal to) 2.31 is 2.

Floor Function : the greatest integer that is less than or equal to x.  is floor function .

Ceiling Function: the least integer that is greater than or equal to x. is ceiling function.


Q 3: Explain Sorting String  and character datatype ?

Sorting string :

To sort strings in alphabetical order in C++ programming, you have to ask to the user to enter the two string, now start comparing the strings, if found then make a t variable of same type, and place the first string to the t, then place second string to the first, then place t to the second string using the function strcpy(), and continue until last as shown in the following program.

Program for sorting of string in c language :

 

/* C++ Program - Sort String in Alphabetical Order */
        
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
void main()
{
    //clrscr();
    char str[5][20], t[20];
    int i, j;
    cout<<"Enter any five string (name) : ";
    for(i=0; i<5; i++)
    {
        cin>>str[i];
    }
    for(i=1; i<5; i++)
    {
        for(j=1; j<5; j++)
        {
            if(strcmp(str[j-1], str[j])>0)
            {
                strcpy(t, str[j-1]);
                strcpy(str[j-1], str[j]);
                strcpy(str[j], t);
            }
        }
    }
    cout<<"Strings (Names) in alphabetical order : \n";
    for(i=0; i<5; i++)
    {
        cout<

Character Data TYPE :

In computer programming, information is stored in a computer memory with different data types. We must know what is to be stored in a computer memory,whether it is a simple number, a letter or a very large number.

The CHAR data type is used for storing fixed length character strings with a maximum size of 2000 bytes. String values will be space-padded before being stored on disk.


Q 4: Explain 1D and 2D array , and representation of 2D in memory ?

Array

An array is a collection of data elements of same data type. It is described by a single name and each element of an array is referenced by using array name and its subscript no.

Declaration of Array

Type arrayName[numberOfElements];

For example,
int Age[5] ;
float cost[30];

array c++

Initialization of One Dimensional Array

An array can be initialized along with declaration. For array initialization it is required to place the elements separated by commas enclosed within braces.
int A[5] = {11,2,23,4,15};
It is possible to leave the array size open. The compiler will count the array size.
int B[] = {6,7,8,9,15,12};

 

Program of 1D array :

// arrays example
#include <iostream>
using namespace std;

int foo [] = {16, 2, 77, 40, 12071};
int n, result=0;

int main ()
{
  for ( n=0 ; n<5 ; ++n )
  {
    result += foo[n];
  }
  cout << result;
  return 0;
}
#include <iostream>
using namespace std;

int main() {
    int n[5];
    cout<<"Enter 5 numbers: ";
/*  Storing 5 number entered by user in an array using for loop. */
    for (int i = 0; i < 5; ++i) {
        cin>>n[i];
    }
    
    cout<<"First number: "<<n[0]<<endl;  // first element of an array is n[0]
    cout<<"Last number: "<<n[4];        // last element of an array is n[SIZE_OF_ARRAY - 1]
    return 0;
}

Program : Two Dimensional Array

You can initialise a multidimensional array in more than one way. Consider this examples to initialise two dimensional array.

int test[2][3] = {2, 4, -5, 9, 0, 9};

Better way to initialise this array with same array elements as above.

int  test[2][3] = { {2, 4, 5}, {9, 0 0}};

C++ Program to display all elements of an initialised two dimensional array.

#include <iostream>
using namespace std;

int main() {
    int test[3][2] = {
        {2, -5},
        {4, 0},
        {9, 1}
    };
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 2; ++j) {
            cout<< "test["<< i << "][" << ;j << "] = " << test[i][j]<<endl;
        }
    }
    return 0;
}

Q5:


Q6 : Explain Over Flow , Under Flow , and Garbage Collection ?

overflow 

An error that occurs when the computer attempts to handle a number that is too large for it. Every computer has a well-defined range of values that it can represent. If during execution of a program it arrives at a number outside this range, it will experience an overflow error. Overflow errors are sometimes referred to as overflow conditions.

When it comes to its limit and yet another operation tries to PUSH data onto the stack then a ‘stack overflow‘ occurs. When this happens it often causes the program to crash. It is up to the software programmer to ensure that the stack does not overflow.

If the stack is empty and yet a POP operation is attempted, this is called an ‘stack underflow‘ and can cause a program to crash. The software programmer should check that the stack is not empty before attempting a POP operation.


Q 7: Insert value in to the sorted link list ?

Step I:              [List empty?] If START = NULL, then:

Set LOC := NULL, and Return.

Step II:           [Special case?] If ITEM < INFO[START], then:

Set LOC := NULL, and Return.

Step III:        Set SAVE := START and  PTR := LINK[START]. [Initialize pointers.]

Step IV:        Repeat step 5 while PTR != NULL:

Step V:           If ITEM < INFO[PTR], then:

Set LOC := SAVE and Return.

Else:

Set SAVE := PTR, and

PTR := LINK[PTR]. [Update pointers.]

[End of If structure.]

[End of step 4 loop.]

Step VI:        Set LOC := SAVE.

Step VII:     Return.


Q8: Explain FIFO structure and its representation ?

FIFO” stands for first-in, first-out, meaning that the oldest inventory items are recorded as sold first but do not necessarily mean that the exact oldest physical object has been tracked and sold. In other words, the cost associated with the inventory that was purchased first is the cost expensed first.

In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed.


 

Q9 :

Recursion is a programming method where you define a function in terms of itself. The function generally calls itself with slightly modified parameters (in order to converge).

Divide and conquer is when you split a problem into non-overlapping sub-problems. For example, in mergesort, you split the array into two halves and sort them and then merge them back. You divided the problem into two sub-problems, solved them and got a solution to the original problem. Note that we use recursion to solve the sub-problems

divide_conquer_1_step

  1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
  2. Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.

-Divide the given problem instance into sub problems

  • Conquer the subproblems by solving them recursively

 

data_____________________________________________________________________________________________

Q :

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C++ Program To Implement Singly Linked List

/*
* C++ Program to Implement Singly Linked List
/
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
/

* Node Declaration
/
struct node
{
int info;
struct node *next;
}
start;

/*
* Class Declaration
/
class single_llist
{
public:
node
create_node(int);
void insert_begin();
void insert_pos();
void insert_last();
void delete_pos();
void sort();
void search();
void update();
void reverse();
void display();
single_llist()
{
start = NULL;
}
};

/*
* Main :contains menu
*/
main()
{
int choice, nodes, element, position, i;
single_llist sl;
start = NULL;
while (1)
{
cout<<endl<<“———————————“<<endl;
cout<<endl<<“Operations on singly linked list”<<endl;
cout<<endl<<“———————————“<<endl;
cout<<“1.Insert Node at beginning”<<endl;
cout<<“2.Insert node at last”<<endl;
cout<<“3.Insert node at position”<<endl;
cout<<“4.Sort Link List”<<endl;
cout<<“5.Delete a Particular Node”<<endl;
cout<<“6.Update Node Value”<<endl;
cout<<“7.Search Element”<<endl;
cout<<“8.Display Linked List”<<endl;
cout<<“9.Reverse Linked List “<<endl;
cout<<“10.Exit “<<endl;
cout<<“Enter your choice : “;
cin>>choice;
switch(choice)
{
case 1:
cout<<“Inserting Node at Beginning: “<<endl;
sl.insert_begin();
cout<<endl;
break;
case 2:
cout<<“Inserting Node at Last: “<<endl;
sl.insert_last();
cout<<endl;
break;
case 3:
cout<<“Inserting Node at a given position:”<<endl;
sl.insert_pos();
cout<<endl;
break;
case 4:
cout<<“Sort Link List: “<<endl;
sl.sort();
cout<<endl;
break;
case 5:
cout<<“Delete a particular node: “<<endl;
sl.delete_pos();
break;
case 6:
cout<<“Update Node Value:”<<endl;
sl.update();
cout<<endl;
break;
case 7:
cout<<“Search element in Link List: “<<endl;
sl.search();
cout<<endl;
break;
case 8:
cout<<“Display elements of link list”<<endl;
sl.display();
cout<<endl;
break;
case 9:
cout<<“Reverse elements of Link List”<<endl;
sl.reverse();
cout<<endl;
break;
case 10:
cout<<“Exiting…”<<endl;
exit(1);
break;
default:
cout<<“Wrong choice”<<endl;
}
}
}

/*
* Creating Node
*/
node *single_llist::create_node(int value)
{
struct node *temp, *s;
temp = new(struct node);
if (temp == NULL)
{
cout<<“Memory not allocated “<<endl;
return 0;
}
else
{
temp->info = value;
temp->next = NULL;
return temp;
}
}

/*
* Inserting element in beginning
*/
void single_llist::insert_begin()
{
int value;
cout<<“Enter the value to be inserted: “;
cin>>value;
struct node *temp, *p;
temp = create_node(value);
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
p = start;
start = temp;
start->next = p;
}
cout<<“Element Inserted at beginning”<<endl;
}

/*
* Inserting Node at last
*/
void single_llist::insert_last()
{
int value;
cout<<“Enter the value to be inserted: “;
cin>>value;
struct node *temp, *s;
temp = create_node(value);
s = start;
while (s->next != NULL)
{
s = s->next;
}
temp->next = NULL;
s->next = temp;
cout<<“Element Inserted at last”<<endl;
}

/*
* Insertion of node at a given position
*/
void single_llist::insert_pos()
{
int value, pos, counter = 0;
cout<<“Enter the value to be inserted: “;
cin>>value;
struct node *temp, *s, *ptr;
temp = create_node(value);
cout<<“Enter the postion at which node to be inserted: “;
cin>>pos;
int i;
s = start;
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos == 1)
{
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
ptr = start;
start = temp;
start->next = ptr;
}
}
else if (pos > 1 && pos <= counter)
{
s = start;
for (i = 1; i < pos; i++)
{
ptr = s;
s = s->next;
}
ptr->next = temp;
temp->next = s;
}
else
{
cout<<“Positon out of range”<<endl;
}
}

/*
* Sorting Link List
*/
void single_llist::sort()
{
struct node *ptr, *s;
int value;
if (start == NULL)
{
cout<<“The List is empty”<<endl;
return;
}
ptr = start;
while (ptr != NULL)
{
for (s = ptr->next;s !=NULL;s = s->next)
{
if (ptr->info > s->info)
{
value = ptr->info;
ptr->info = s->info;
s->info = value;
}
}
ptr = ptr->next;
}
}

/*
* Delete element at a given position
*/
void single_llist::delete_pos()
{
int pos, i, counter = 0;
if (start == NULL)
{
cout<<“List is empty”<<endl;
return;
}
cout<<“Enter the position of value to be deleted: “;
cin>>pos;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start = s->next;
}
else
{
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos > 0 && pos <= counter)
{
s = start;
for (i = 1;i < pos;i++)
{
ptr = s;
s = s->next;
}
ptr->next = s->next;
}
else
{
cout<<“Position out of range”<<endl;
}
free(s);
cout<<“Element Deleted”<<endl;
}
}

/*
* Update a given Node
*/
void single_llist::update()
{
int value, pos, i;
if (start == NULL)
{
cout<<“List is empty”<<endl;
return;
}
cout<<“Enter the node postion to be updated: “;
cin>>pos;
cout<<“Enter the new value: “;
cin>>value;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start->info = value;
}
else
{
for (i = 0;i < pos – 1;i++)
{
if (s == NULL)
{
cout<<“There are less than “<<pos<<” elements”;
return;
}
s = s->next;
}
s->info = value;
}
cout<<“Node Updated”<<endl;
}

/*
* Searching an element
*/
void single_llist::search()
{
int value, pos = 0;
bool flag = false;
if (start == NULL)
{
cout<<“List is empty”<<endl;
return;
}
cout<<“Enter the value to be searched: “;
cin>>value;
struct node *s;
s = start;
while (s != NULL)
{
pos++;
if (s->info == value)
{
flag = true;
cout<<“Element “<<value<<” is found at position “<<pos<<endl;
}
s = s->next;
}
if (!flag)
cout<<“Element “<<value<<” not found in the list”<<endl;
}

/*
* Reverse Link List
*/
void single_llist::reverse()
{
struct node *ptr1, *ptr2, *ptr3;
if (start == NULL)
{
cout<<“List is empty”<<endl;
return;
}
if (start->next == NULL)
{
return;
}
ptr1 = start;
ptr2 = ptr1->next;
ptr3 = ptr2->next;
ptr1->next = NULL;
ptr2->next = ptr1;
while (ptr3 != NULL)
{
ptr1 = ptr2;
ptr2 = ptr3;
ptr3 = ptr3->next;
ptr2->next = ptr1;
}
start = ptr2;
}

/*
* Display Elements of a link list
*/
void single_llist::display()
{
struct node *temp;
if (start == NULL)
{
cout<<“The List is Empty”<<endl;
return;
}
temp = start;
cout<<“Elements of list are: “<<endl;
while (temp != NULL)
{
cout<<temp->info<<“->”;
temp = temp->next;
}
cout<<“NULL”<<endl;
}

 

Advertisements