Data Structure Compiled Note

September 1, 2016 Data Structure and Algorithm Analysis
Data Structure and Algorithm Analysis using C++
September 01, 2016

1 Compiled By: Maregu Assefa
Chapter One
1. Introduction to Data Structures
Data Structure is a way of collecting and organizing data in such a way that we can perform
operations on these data in an effective way. Data Structures is about rendering data elements in
terms of some relationship, for better organization and storage. Data may be organized in many
different ways; the logical or mathematical model of a particular organization of data is called a
data structure.
For example, we have data player's name "Adane" and age 34. Here "Adane" is of
String data type and 34 is of integer data type. We can organize this data as a record like Player record.
Now we can collect and store player's records in a file or database as a data structure. For example:
"Adane" 34, "Selhadin" 31, "Asrat" 33.
In simple language, Data Structures are structures programmed to store ordered data, so that
various operations can be performed on it easily.
Basic types of Data Structures

As we discussed above, anything that can store data can be called as a data structure, hence Integer,
Float, Boolean, Char etc, all are data structures. They are known as Primitive Data Structures.
Then we also have some complex Data Structures, which are used to store large and connected data.
Some example of Abstract Data Structure is:
 Linked List
 Tree
 Graph
 Stack, Queue etc.
All these data structures allow us to perform different operations on data. We select these data
structures based on which type of operation is required. We will look into these data structures in
more details in our later lessons.

Algorithm
What is Algorithm?
An algorithm is a finite set of instructions or logic, written in order, to accomplish a certain
predefined task. Algorithm is not the complete code or program, it is just the core logic (solution) of
a problem, which can be expressed either as an informal high level description as pseudo code or
using a flowchart.
An algorithm is said to be efficient and fast, if it takes less time to execute and consumes less
memory space. The performance of an algorithm is measured on the basis of following properties:
1. Time Complexity
2. Space Complexity
Space Complexity
Space complexity is the amount of memory space required by the algorithm, during the course of its
execution. Space complexity must be taken seriously for multi-user systems and in situations where
limited memory is available.
An algorithm generally requires space for following components:

 Instruction Space: It’s the space required to store the executable version of the program.
This space is fixed, but varies depending upon the number of lines of code in the program.
 Data Space: It’s the space required to store all the constants and variables value.
 Environment Space: It’s the space required to store the environment information needed to
resume the suspended function.
Time Complexity
Time Complexity is a way to represent the amount of time needed by the program to run to
completion. Time complexity of an algorithm signifies the total time required by the program to run to
completion. The time complexity of algorithms is most commonly expressed using the big O
notation.
Time Complexity is most commonly estimated by counting the number of elementary functions
performed by the algorithm. And since the algorithm's performance may vary with different types of
input data, hence for an algorithm we usually use the worst-case Time complexity of an algorithm
because that is the maximum time taken for any input size.
Calculating Time Complexity

Now let’s tap onto the next big topic related to Time complexity, which is How to Calculate Time Complexity. It becomes
very confusing some times, but we will try to explain it in the simplest way.
Now the most common metric for calculating time complexity is Big O notation. This removes all constant factors so that
the running time can be estimated in relation to N, as N approaches infinity. In general you can think of it like this:
statement;
Above we have a single statement. Its Time Complexity will be Constant. The running time of the statement will not
change in relation to N.
for(i=0; i < N; i++)
{
statement;
}
The time complexity for the above algorithm will be Linear. The running time of the loop is directly proportional to N.
When N doubles, so does the running time.
for(i=0; i < N; i++)

{
for(j=0; j < N; j++)
{
statement;
}
}
This time, the time complexity for the above code will be Quadratic. The running time of the two loops is proportional to
the square of N. When N doubles, the running time increases by N * N.
while(low <= high)

{
mid = (low + high) / 2;
if (target < list[mid])
high = mid - 1;
else if (target > list[mid])
low = mid + 1;
else break;
}
This is an algorithm to break a set of numbers into halves, to search a particular field(we will study this in detail later).
Now, this algorithm will have a Logarithmic Time Complexity. The running time of the algorithm is proportional to the
number of times N can be divided by 2(N is high-low here). This is because the algorithm divides the working area in half
with each iteration.
void quicksort(int list[], int left, int right)
{
int pivot = partition(list, left, right);
quicksort(list, left, pivot - 1);
quicksort(list, pivot + 1, right);
}
Taking the previous algorithm forward, above we have a small logic of Quick Sort(we will study this in detail later). Now
in Quick Sort, we divide the list into halves every time, but we repeat the iteration N times(where N is the size of list).
Hence time complexity will be N*log( N ). The running time consists of N loops (iterative or recursive) that are
logarithmic, thus the algorithm is a combination of linear and logarithmic.
NOTE : In general, doing something with every item in one dimension is linear, doing something with every item in two
dimensions is quadratic, and dividing the working area in half is logarithmic.

Types of Notations for Time Complexity

Now we will discuss and understand the various notations used for Time Complexity.
1. Big Oh denotes "fewer than or the same as" <expression> iterations.
2. Big Omega denotes "more than or the same as" <expression> iterations.
3. Big Theta denotes "the same as" <expression> iterations.
4. Little Oh denotes "fewer than" <expression> iterations.
5. Little Omega denotes "more than" <expression> iterations.
Understanding Notations of Time Complexity with Example

O (expression) is the set of functions that grow slower than or at the same rate as expression.
Omega (expression) is the set of functions that grow faster than or at the same rate as expression.
Theta (expression) consist of all the functions that lie in both O(expression) and Omega(expression).
Suppose you've calculated that an algorithm takes f(n) operations, where,
f(n) = 3*n^2 + 2*n + 4. // n^2 means square of n
Since this polynomial grows at the same rate as n^2, then you could say that the function f lies in the set Theta(n^2). (It
also lies in the sets O(n^2) and Omega(n^2) for the same reason.)
The simplest explanation is, because Theta denotes the same as the expression. Hence, as f(n) grows by a factor of n^2,
the time complexity can be best represented as Theta(n^2).

Chapter Two
2. Abstract Data Types (ADTs)
Data may be organized in many different ways; the logical or mathematical model of a particular
organization of data is called a data structure.
Data structure is represented as: Data structure = Organized data + Allowed Operations.
Data structures are classified as either linear or nonlinear.
Linear Data Structure:

The elements form a sequence, i.e., linear list. Examples of linear data structures are arrays, linked lists,
stacks and queues.
Non Linear Data Structure:

The elements do not form a sequence. Examples of non-linear data structures are trees and graphs.
A linked list is a collection of data elements called nodes. All nodes of a linked list are linked by
pointers. Each node contains:
i) The data item
ii) A pointer to the next node.
2.1. Introduction to Linked Lists

Linked List is a linear data structure and it is very common data structure which consists of group of nodes in a sequence
which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain.
Linked Lists are used to create trees and graphs.
Advantages of Linked Lists
 They are a dynamic in nature which allocates the memory when required.
 Insertion and deletion operations can be easily implemented.

 Stacks and queues can be easily executed.

 Linked List reduces the access time.
Disadvantages of Linked Lists
 The memory is wasted as pointers require extra memory for storage.

 No element can be accessed randomly; it has to access each node sequentially.
 Reverse Traversing is difficult in linked list.
Applications of Linked Lists
 Linked lists are used to implement stacks, queues, graphs, etc.

 Linked lists let you insert elements at the beginning and end of the list.
 In Linked Lists we don’t need to know the size in advance.
Types of Linked Lists
 Singly Linked List: Singly linked lists contain nodes which have a data part as well as an address part i.e. next,
which points to the next node in sequence of nodes. The operations we can perform on singly linked lists are insertion,
deletion and traversal.
 Doubly Linked List: In a doubly linked list, each node contains two links the first link points to the previous node
and the next link points to the next node in the sequence.

 Circular Linked List: In the circular linked list the last node of the list contains the address of the first node and
forms a circular chain.
Arrays Vs Linked lists
For storing similar data in memory we can use either an array or a linked list. Arrays are simple to
understand and elements of an array are easily accessible. But arrays suffer from the following
limitations:
 Arrays have fixed dimensions: Once the size of an array is decided it cannot be decrease or
increase during execution.
 Arrays elements are always stored in contiguous memory locations. Even though the total space
requirement of the array can be met through a combination of non-contiguous blocks of memory,
we would still not be allowed to create the array.
 Insertion or deletion of an element in the array is bulky. This is because during insertion or
deletion each element after the specified position has to be shifted on position to the right (for
insertion case) or one position to the left (for deletion operation).
Linked list solves all these disadvantages.
 A linked list can grow and shrink in size during its lifetime. That means there is no maximum size
of a linked list.
 The second advantage of linked list is that, nodes are stored in different memory locations.
 Unlike arrays, while inserting or deleting the nodes of the linked list, shifting of nodes is not
required.
Singly Linked Lists
Linked lists are the most basic self-referential structures. Linked lists allow you to have a chain of structs
with related data.
Linked List is a very common data structure often used to store similar data in memory. While the
elements of an array occupy contiguous memory locations, those of a linked list are not constrained to be
stored in adjacent locations. The individual elements are stored somewhere in memory, rather like a

family dispersed, but still bound together. The order of the elements is maintained by explicit links
between them.
Creating Linked Lists in C++

A linked list is a data structure that is built from structures and pointers. It forms a chain of "nodes" with
pointers representing the links of the chain and holding the entire thing together. A linked list can be
represented by a diagram like this one:
This linked list has four nodes in it, each with a link to the next node in the series. The last node has a link
to the special value NULL, which any pointer (whatever its type) can point to, to show that it is the last
link in the chain. There is also another special pointer, called Head (also called Start), which points to the
first link in the chain so that we can keep track of it.
Defining the data structure for a linked list

The key part of a linked list is a structure, which holds the data for each node (the name, address, age or
whatever for the items in the list), and, most importantly, a pointer to the next node. Here we have given
the structure of a typical node:
struct node //structure name
char name[20]; // Name of up to 20 letters
int age;
float height;
node *next;// Pointer to next node
} *head= NULL;

The important part of the structure is the line before the closing curly brackets. This gives a pointer to the
next node in the list. This is the only case in C++ where you are allowed to refer to a data type (in this
case node) before you have even finished defining it!
We have also declared a pointer called head that will permanently point to the start of the list. To start
with, there are no nodes in the list, which is why head is set to NULL.
Adding a node to the list

There are three positions to insert a node to the list
A. At the beginning of the list
B. At the end of the list
C. Somewhere in the middle of the list.
A. Insertion at the beginning
Adding a node to the beginning of a linked list is performed in four steps
 Create a new node in memory
 Initialize the info member to a particular integer
 The node is being added to the front of the list, the next member becomes a pointer to the first
node of the list, that is the current value of head
 The new node now precedes all the nodes in the list, but we need to update the value of head
to reflect this fact. Therefore, head is made to point to the newly created node.
void addbegn(){
node *temp;
temp=new node;
cout<<"Enter Id :";
cin>>temp->id;
cout<<"Enter Age :";

cin>>temp->age;
cout<<"Enter Name :";
cin>>temp->name;
temp->next=NULL;
if(Head == NULL)
Head = temp;
else
temp->next = Head;
Head = temp;

B. Insert at the end of the list

Adding a node to the end of the list consists of five steps
 Create a new node in memory
 Initialize the info member to a particular integer
 The node is being added at the end of the list, the next member is set to null
 The node is included in the list by making the next member of the last node in the list point to
the newly created node.
 The new node now follows all the nodes in the list, but we need to update the value of tail to
reflect this fact. Therefore, tail is made to point to the newly created node.
Firstly, we declare the space for a pointer item and assign a temporary pointer to it. This is done using the
new statement as follows:
temp = new node;
We can refer to the new node as *temp, i.e. "the node that temp points to". When the fields of this
structure are referred to, brackets can be put round the *temp part, as otherwise the compiler will think we
are trying to refer to the fields of the pointer. Alternatively, we can use the arrow pointer notation. That's
what we shall do here.
Having declared the node, we ask the user to fill in the details of the person, i.e. the name, age, address or
whatever:
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->next = NULL;
The last line sets the pointer from this node to the next to NULL, indicating that this node, when it is
inserted in the list, will be the last node. Having set up the information, we have to decide what to do with
the pointers. Of course, if the list is empty to start with, there's no problem - just set the Start pointer to
point to this node (i.e. set it to the same value as temp):
if (start_ptr == NULL)
start_ptr = temp;

It is harder if there are already nodes in the list. In this case, the secret is to declare a second pointer,
temp2, to step through the list until it finds the last node.
temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->next != NULL)
{ temp2 = temp2->next; // Move to next link in chain

}
The loop will terminate when temp2 points to the last node in the chain, and it knows when this happened
because the nxt pointer in that node will point to NULL. When it has found it, it sets the pointer from that
last node to point to the node we have just declared:
temp2->next = temp;
The link temp2->next in this diagram is the link joining the last two nodes. The full code for adding a
node at the end of the list is shown below, in its own little function:
void add_node_at_end ()
{ node *temp, *temp2; // Temporary pointers
// Reserve space for new node and fill it with data
temp = new node;
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;
cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->nxt = NULL;
// Set up link to this node

start_ptr = temp;
else
{ temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{ temp2 = temp2->nxt;
// Move to next link in chain
temp2->nxt = temp;
Displaying the list of nodes

Having added one or more nodes, we need to display the list of nodes on the screen. This is comparatively
easy to do. Here is the method:
1. Set a temporary pointer to point to the same thing as the start pointer.
2. If the pointer points to NULL, display the message "End of list" and stop.
3. Otherwise, display the details of the node pointed to by the start pointer.
4. Make the temporary pointer point to the same thing as the next pointer of the node it is currently
indicating.
5. Jump back to step 2.
The temporary pointer moves along the list, displaying the details of the nodes it comes across. At each
stage, it can get hold of the next node in the list by using the next pointer of the node it is currently
pointing to. Here is the C++ code that does the job:
temp = start_ptr;
do
{ if (temp == NULL)
cout << "End of list" << endl;

else
{ // Display details for what temp points to
cout << "Name : " << temp->name << endl;
cout << "Age : " << temp->age << endl;

cout << "Height : " << temp->height << endl;
cout << endl; // Blank line
// Move to next node (if present)
temp = temp->next;
} while (temp != NULL);

Check through this code, matching it to the method listed above. It helps if you draw a diagram on paper
of a linked list and work through the code using the diagram.
Deleting a node from the list

When it comes to deleting nodes, we have three choices:
A. Delete a node from the begin of the list,
B. Delete from the end of the list,
C. Delete one from somewhere in the middle.
A. Delete a node from the begin
temp = start_ptr; // Make the temporary pointer
// identical to the start pointer
Now that the first node has been safely tagged (so that we can refer to it even when the start
pointer has been reassigned), we can move the start pointer to the next node in the chain:
start_ptr = start_ptr->next; // Second node in chain.
delete temp; // Wipe out original start node
Here is the function that deletes a node from the start (head):

void deletebegin()
node *temp;
temp = head;
head =head->next;
delete temp;
B. Delete a node from the end

Deleting a node from the end of the list is harder, as the temporary pointer must find where the end of the
list is by hopping along from the start. This is done using code that is almost identical to that used to
insert a node at the end of the list. It is necessary to maintain two temporary pointers, temp1 and temp2.
The pointer temp1 will point to the last node in the list and temp2 will point to the previous node. We
have to keep track of both as it is necessary to delete the last node and immediately afterwards, to set the
next pointer of the previous node to NULL (it is now the new last node).
1. Look at the start pointer. If it is NULL, then the list is empty, so print out a "No nodes to delete"
message.
2. Make temp1 point to whatever the start pointer is pointing to.
3. If the next pointer of what temp1 indicates is NULL, then we've found the last node of the list, so
jump to step 7.
4. Make another pointer, temp2, point to the current node in the list.
5. Make temp1 point to the next item in the list.
6. Go to step 3.
7. If you get this far, then the temporary pointer, temp1, should point to the last item in the list and
the other temporary pointer, temp2, should point to the last-but-one item.
8. Delete the node pointed to by temp1.
9. Mark the next pointer of the node pointed to by temp2 as NULL - it is the new last node.
Let's try it with a rough drawing. This is always a good idea when you are trying to understand an abstract
data type. Suppose we want to delete the last node from this list:
Firstly, the start pointer doesn't point to NULL, so we don't have to display a "Empty list, wise
guy!" message. Let's get straight on with step2 - set the pointer temp1 to the same as the start
pointer:

The next pointer from this node isn't NULL, so we haven't found the end node. Instead, we set the
pointer temp2 to the same node as temp1
and then move temp1 to the next node in the list:
Going back to step 3, we see that temp1 still doesn't point to the last node in the list, so we make
temp2 point to what temp1 points to
start_ptr
NULL
temp 2 temp1
and temp1 is made to point to the next node along:
Eventually, this goes on until temp1 really is pointing to the last node in the list, with temp2
pointing to the penultimate node:
start_ptr
NULL

temp 2 temp1
Now we have reached step 8. The next thing to do is to delete the node pointed to by temp1
and set the next pointer of what temp2 indicates to NULL:
Note: start_prt means head.
void delete_end_node()
{
node *temp1, *temp2;
cout << "The list is empty!" << endl;
else
{ temp2 = temp1;
temp1 = temp1->next;
delete temp1;
temp2->next = NULL;
The code seems a lot shorter than the explanation!
Now, the sharp-witted amongst you will have spotted a problem. If the list only contains one node, the
code above will malfunction. This is because the function goes as far as the temp1 = start_ptr statement,
but never gets as far as setting up temp2. The code above has to be adapted so that if the first node is also
the last (has a NULL next pointer), then it is deleted and the start_ptr pointer is assigned to NULL. In this
case, there is no need for the pointer temp2:

void delete_end_node()
{ node *temp1, *temp2;
cout << "The list is empty!" << endl;
else
if (temp1->nxt == NULL) // This part is new!
{ delete temp1;
start_ptr = NULL;
else{
temp2 = temp1;
temp1 = temp1->next;
delete temp1;
temp2->next = NULL;
Doubly Linked Lists
That sounds even harder than a linked list! Well, if you've mastered how to do singly linked lists, then it
shouldn't be much of a leap to doubly linked lists.
A doubly linked list is one where there are links from each node in both directions: We can traverse in
both directions in a doubly linked list as each and every node of a double linked list contains address of
next node along with address of previous node also. Thus a node in a doubly linked list contains at least 3
fields.
1. Data field.
2. Address of next node.
3. Address of previous node.
Linear doubly linked list without header node

You will notice that each node in the list has two pointers; one to the next node and one to the previous
one - again, the ends of the list are defined by NULL pointers. Also there is no pointer to the start of the
list. Instead, there is simply a pointer to some position in the list that can be moved left or right.
The reason we needed a start pointer in the ordinary linked list is because, having moved on from one
node to another, we can't easily move back, so without the start pointer, we would lose track of all the
nodes in the list that we have already passed. With the doubly linked list, we can move the current pointer
backwards and forwards at will.
 We can have also linear doubly linked list with header node point to the first node.
struct node{
int data;
struct node *left;
struct node *right;
}*head ;
Head
10 20 30
NULL Left Left Left
Right Right Right NULL
Creating Doubly Linked Lists

The nodes for a doubly linked list would be defined as follows:
struct node{
char name[20];
node *next; // Pointer to next node
node *prv; // Pointer to previous node
};
node *current;
current = new node;
current->name = "Fred";
current->next = NULL;
current->prv = NULL;
We have also included some code to declare the first node and set its pointers to NULL. It gives the
following situation:

We still need to consider the directions 'forward' and 'backward', so in this case, we will need to define
functions to add a node to the start of the list (left-most position) and the end of the list (right-most
position).
Adding a Node to a Doubly Linked List
void addbegin()
node *temp;
temp=new node;
cout<<"enter value :";
cin>>temp->mark;
temp->next=NULL;
temp->prev=NULL;
if(current==NULL)
current=temp;
else{
temp->next=current;
current=temp;
void addend()
{
node *temp;
temp=new node;
cout<<"enter value :";
cin>>temp->mark;
temp->next=NULL;
temp->prev=NULL;
if(current== NULL)
current=temp;
else
{
while(current->next!=NULL)

current=current->next;
}
current->next=temp;
temp->prev=current;
Here, the new name is passed to the appropriate function as a parameter. We'll go through the function for
adding a node to the right-most end of the list. The method is similar for adding a node at the other end.
Firstly, a temporary pointer is set up and is made to march along the list until it points to last node in the
list.
Start_Ptr
After that, a new node is declared, and the name is copied into it. The nxt pointer of this new node is set to
NULL to indicate that this node will be the new end of the list.
The prv pointer of the new node is linked into the last node of the existing list.
The nxt pointer of the current end of the list is set to the new node.
Display a node from double linked list

void display()
if(current==NULL)
cout<<"The list is empty"<<endl;
else
while(current->prev!=NULL)
current=current->prev;
while(current!=NULL)
{
cout<<current->mark<<endl;
current=current->next;

Deleting a Node from a Doubly Linked List

When it comes to deleting nodes, we have three choices: Delete a node from the start (front end) of the
list, delete one from the end (tail end) of the list, or delete one form somewhere in the middle.
Hear let as see, to delete node from front end of a double lined list (for others workout by your on).
Assume that the doubly linked list contains 4 nodes as shown in the above figure.
Head
40 30 20 10
NULL Left Left Left Left
Right Right Right Right

NULL
q= head;
q Head
head= q->right;
head->left=NULL;
x=q->data; 40 30 20 10
delete(q);
NULL Left Left Left Left
Right Right Right Right

NULL
NULL
Head
30 20 10
NULL Left Left Left
Right Right Right

NULL
Circular Linked List
Circular Linked List is little more complicated linked data structure. In the circular linked list we can insert elements
anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous
memory. In the circular linked list the previous element stores the address of the next element and the last element stores
the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The
circular linked list has a dynamic size which means the memory can be allocated when it is required.

Application of Circular Linked List
 The real life application where the circular linked list is used is our Personal Computers, where multiple applications
are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for
running. The Operating System keeps on iterating over the linked list until all the applications are completed.
 Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps
on moving forward as a player's chance ends.
 Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and
REAR in memory all the time, where as in Circular Linked List, only one pointer is required.
Implementing Circular Linked List

Implementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only
difference being that, in circular linked list the last Node will have its next point to the Head of the List. In Linear linked
list the last Node simply holds NULL in its next pointer.
So this will be our Node class, as we have already studied in the lesson, it will be used to form the List.
class Node {
public:
int data;
//pointer to the next node
node* next;
node() {
data = 0;
next = NULL;
node(int x) {
data = x;
next = NULL;

Circular Linked List

Circular Linked List class will be almost same as the Linked List class that we studied in the previous lesson, with a few
differences in the implementation of class methods.
class CircularLinkedList {
public:
node *head;
//declaring the functions
//function to add Node at front
int addAtFront(node *n);
//function to check whether Linked list is empty
int isEmpty();
//function to add Node at the End of list
int addAtEnd(node *n);
//function to delete any Node
node* deleteNode(int x);
CircularLinkedList() {
head = NULL;
}
}
Insertion at the Beginning

Steps to insert a Node at beginning:
1. The first Node is the Head for any Linked List.

2. When a new Linked List is instantiated, it just has the Head, which is Null.
3. Else, the Head holds the pointer to the first Node of the List.
4. When we want to add any Node at the front, we must make the head point to it.
5. And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of new
List) or the pointer to the first Node of the List.
6. The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.
int CircularLinkedList :: addAtFront(node *n) {
int i = 0;
/* If the list is empty */
if(head == NULL) {
n->next = head;
//making the new Node as Head
head = n;
i++;
else {
n->next = head;

//get the Last Node and make its next point to new Node
Node* last = getLastNode();
last->next = n;
//also make the head point to the new first Node
head = n;
i++;
//returning the position where Node is added
return i;
Insertion at the End

Steps to insert a Node at the end:
1. If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
2. If the Linked List is not empty then we find the last node, and make it' next to the new Node, and make the next of the
newly added Node point to the Head of the List.
int CircularLinkedList :: addAtEnd(node *n) {
//If list is empty
if(head == NULL) {
//making the new Node as Head
head = n;
//making the next pointer of the new Node as Null
n->next = NULL;
else {
//getting the last node

node *last = getLastNode();
last->next = n;
//making the next pointer of new node point to head
n->next = head;
}
}
Deleting a Node from the List

Deleting a node can be done in many ways, like we first search the Node with data which we want to delete and then we
delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search
method to locate it and will then remove the Node from the List.
To remove any Node from the list, we need to do the following:
 If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element
from the Node to be deleted. And update the next pointer of the Last Node as well.

 If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the Node
next to it.
 If the Node is at the end, then remove it and make the new last node point to the head.
node* CircularLinkedList :: deleteNode(int x) {

//searching the Node with data x
node *n = search(x);
node *ptr = head;
if(ptr == NULL) {
cout << "List is empty";
return NULL;
else if(ptr == n) {
ptr->next = n->next;
return n;
}
else {
while(ptr->next != n) {
ptr = ptr->next;
ptr->next = n->next;
return n;
2.2. Stacks
Stack is an abstract data type with a bounded (predefined) capacity. It is a simple data structure that allows adding and
removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element
that can be removed is the element that was at the top of the stack, just like a pile of objects.

Basic features of Stack
1. Stack is an ordered list of similar data type.
2. Stack is a LIFO structure. (Last in First out).
3. push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack.
Both insertion and deletion are allowed at only one end of Stack called Top.
4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely
empty.
Applications of Stack
The simplest application of a stack is to reverse a word. You push a given word to stack - letter by letter - and then pop
letters from the stack.
There are other uses also like: Parsing, Expression Conversion(Infix to Postfix, Postfix to Prefix etc) and many more.
Stack is a simple data structure, in which insertion and deletion occur at the same end. That means that
the last item to be added to a stack is the first item to be removed. It is a LIFO (Last In First Out)
structure.
The operations of insertion and deletion are called PUSH and POP
Push – insert item onto stack
Pop - remove item from stack
Initial Stack Push(8) Pop(8)
TopS=> 8
TopS=> 4 4 TopS=> 4
1 1 1
3 3 3
6 6 6
Unlike an array, stack provides the insertion and deletion of items. So a stack is a dynamic,
constantly changing object.

Linked List Implementation of Stacks:
The main problem was overflow condition which is faced when stacks try to cross size of array. This
problem can be solved by linked implementation. Here we will follow the principle of dynamic
memory allocation. Every time memory will be allocated at runtime, whenever new element is
pushed into the stack. Similarly, memory will be freed when we pop an element from the stack.
When Stack is empty, Pop operation cannot be performed.
Push Operation:
Algorithm
1. Check if stack is empty. If so, create a new node and let Top be a pointer pointing to the new node.
2. if not, create a new node and insert this new node in the beginning and give link with the existing
node. Thus, new node will be on the Top of the stack.
Step 1: As the stack is empty, the first node causes the list to appear as
10
NULL
Step 2:
To Push another item 20 onto stack, now step 2 is executed. This causes another node p, to be created
with info 20 and is inserted in the beginning. If the link, p->next = top, is given the new item is
pushed onto the top of the stack and p=top makes the new node be the top of the stack.
20 10
NULL
void push()
int a;
cout<<"Enter The Size"<<endl;
cin>>a;
for(int i=1;i<=a;i++)
{
stack *temp;
temp=new stack;
cout<<"Enter The Mark"<<endl;
cin>>temp->mark;
if(top==NULL)

top=temp;
top->next=NULL;
}
else
temp->next=top;
top=temp;
Pop Operation:
Algorithm
1. Check if Stack is empty. If it is empty, give the message “Stack Empty”.
2. Else, Display the info part of first part and make the next node as Top. Thus, next
Node will be on the Top of the stack.

void pop()
{
stack *temp1;
if(top==NULL)
cout<<"The stack is empty"<<endl;
else
temp1=top;
top=top->next;
delete temp1;
void display()
stack *temp2;
temp2=top;
cout<<"--------------"<<endl;
if(top==NULL)
cout<<"The stack is Empty"<<endl;

else
while(temp2!=NULL)
{
cout<<temp2->mark<<endl;
temp2=temp2->next;
2.3. Queue Data Structures

Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end
called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also
called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.
The process to add an element into queue is called Enqueue and the process of removal of an element from queue is
called Dequeue.
Basic features of Queue
1. Like Stack, Queue is also an ordered list of elements of similar data types.
2. Queue is a FIFO( First in First Out ) structure.
3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be
removed, to remove the new element.
4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

Applications of Queue
Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one
coming in, also gets out first while the others wait for there turn, like in the following scenarios :
1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service
representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come
first served.
A Queue is an ordered collection of items from which items may be deleted at one end called the
front of the Queue and into which items may be inserted at the other end called the rear of the queue.
Like a stack, a queue is also a list. However, with a queue, insertion is done at one end, while deletion is
performed at the other end.
Accessing the elements of queues follows a First In, First Out (FIFO) order. The first element inserted
into the queue is the first element to be removed. For this reason a queue is sometimes called a FIFO list.
In ordinary English, a queue is defined as a waiting line, like a line of people waiting to purchase tickets,
where the first person in the queue is the first person served.
 Uses two pointers/indices to keep track of information/data.

o Front
o Rear
 has two basic operations:
o enqueue - inserting data at the rear of the queue
o dequeue – removing data at the front of the queue
dequeue enqueue
Front Rear
Front = 0
Empty Queue
Rear = -1
0 1 2 3 4
Front = 0
10 Rear = 0
enqueue - 10

0 1 2 3 4
Front = 0
10 20
enqueue - 20
Rear = 1
0 1 2 3 4
enqueue - 30
10 20 30 40 50
enqueue - 40 Front = 0
0 1 2 3 4
enqueue - 50 Rear = 4
Front = 1
20 30 40 50
x = dequeue(q)
Rear = 4
0 1 2 3 4
Front = 2
30 40 50
x = dequeue(q)
Rear = 4
0 1 2 3 4
void enqueue()
int a;
cout<<"Enter The Size"<<endl;
cin>>a;
queue *temp;
temp=new queue;
cout<<"Enter The Mark"<<endl;
cin>>temp->mark;
temp->next=NULL;
if(front==NULL)
front=temp;
rear=temp;
//top->next=NULL;
else

rear->next=temp;
rear=temp;
}
void dequeue()
queue *temp1;
if(front==NULL)
cout<<"The stack is empty"<<endl;
else if(front->next==NULL)
temp1=front;
front=NULL;
rear=NULL;
delete temp1;
else
temp1=front;
front=front->next;
delete temp1;
A Queue is a particular kind of abstract data type or collection in which the entities in the collectionare
kept in order and the principal (or only) operations on the collection are the addition of entities to the rear
terminal position, known as enqueue, and removal of entities from the front terminal position, known as
dequeue. This makes the queue a First-In-First-Out (FIFO) data structure.
Program to implement Queue using Linked List C++

#include<iostream>
using namespace std;

struct node
int data;
node *next;
}*front = NULL,*rear = NULL,*p = NULL,*np = NULL;
void push(int x)

np = new node;
np->data = x;
np->next = NULL;
if(front == NULL)
front = rear = np;
rear->next = NULL;
else
rear->next = np;
rear = np;
rear->next = NULL;
}
int remove()
int x;
if(front == NULL)
cout<<"empty queuen";
}
else
{
p = front;
x = p->data;
front = front->next;
delete(p);
return(x);
int main()
{
int n,c = 0,x;
cout<<"Enter the number of values to be pushed into queuen";

cin>>n;
while (c < n)
cout<<"Enter the value to be entered into queuen";

cin>>x;
push(x);
c++;
}
cout<<"nnRemoved Valuesnn";
while(true)
if (front != NULL)
cout<<remove()<<endl;
else
break;
return 0;
2.4. Tree Data Structure

A tree is a set of nodes and edges that connect pairs of nodes. It is an abstract model of a hierarchical
structure. Rooted tree has the following structure:
 One node distinguished as root.

 There is a unique path from the root to the each node.
 The number of edges in a path is the length of the path.
Tree Terminologies A
Consider the following tree.
B E F G
C D H I J
K L M
Root: a node without a parent.  A
Internal node: a node with at least one child. A, B, F, I, J
External (leaf) node: a node without a child.  C, D, E, H, K, L, M, G
Ancestors of a node: parent, grandparent, grand-grandparent, etc of a node.

Ancestors of K  A, F, I
Descendants of a node: children, grandchildren, grand-grandchildren etc of a node.

Descendants of F  H, I, J, K, L, M
Depth of a tree/Height of a tree: the length of the longest path from the root to any other node. Or the
depth of the deepest node. 3
Sub tree: a tree consisting of a node and its descendants. F
Degree: The degree of a node is the number of children it has.
Degree of leaf is zero. H I J
Nodes that have degree ZERO are called Leaf nodes or Terminal nodes.
K L M
Binary tree
Binary tree is a tree in which no node can have more than two children or a tree in which each node has at
most two children called left child and right child.
Binary tree is either empty, or it consists of a node called the root together with two binary trees called
Root Root Root

A A A
B C B C C
D E D E E
F E E
the left sub-tree and the right sub-tree.
Strictly binary tree: a binary tree where each node has either 0 or 2 children.
Balanced binary tree: a binary tree where each node except the leaf nodes has left and right children
and all the leaves are at the same level.
Complete binary tree: a binary tree in which the length from the root to any leaf node is either h or h-1
where h is the height of the tree. The deepest level should also be filled from left
to right.

Binary search tree (ordered binary tree)

A binary tree that may be empty, but if it is not empty, it satisfies the following.
 Every node has a key and no two elements have the same key.
 The keys in the right subtree are larger than the keys in the root.
 The keys in the left subtree are smaller than the keys in the root.
 The left and the right subtrees are also binary search trees.
10
6 15
4 8 14 18
7 12 16 19
11 13
Ex1: Creating a binary search tree with the following values.
10 8 15 25 22 30
Step by step creation of a binary search tree.
Root Root Root Root
10 8 10 15 10 25 10
10
8 8 15 8 15
25
Root Root
22 10 30 10
8 15 8 15
25 25
37 22 Compiled By: Maregu Assefa

22 30
Ex2: Creating a binary search tree with the following values.
14 4 15 3 9 18 16 20 7 5 17
Root
14
4 15
4
3 18
3 9
9
16 20
7
7
5 17
5
Operations on Binary Search Tree
A. Inserting a new node

B. Traversing all elements
Consider the following definition of binary search tree.
struct Node
int Num;
Node * Left, *Right;
};
Node *root=NULL;
A. Insertion a new node

When a node is inserted the definition of binary search tree should be preserved. Suppose there is a
binary search tree whose root node is pointed by rootptr and we want to insert a node (that stores 17)
pointed by InsNodePtr.
Case 1: if there is no data in the tree (i.e. rootptr is NULL)
- The node pointed by InsNodePtr should be made the root node.
InsNodePtr rootptr rootptr


17 17
Case 2: if there is data
- Search the appropriate position.
- Insert the node in that position.
InsNodePtr rootptr rootptr
InsertBST() 
17 10 10
6 15 6 15
4 8 14 4 8 14 18
18
7 12 7 12 16 19
16 19
11 13 11 13 17

Insertion Implementation:
void insertBST()
{
int a;
cout<<"Enter the size"<<endl;
cin>>a;
node *newnode,*temp;
temp=new node;
temp=root;
newnode=new node;
cout<<"\nenter number :";
cin>>newnode->num;
newnode->left = NULL;
newnode->right = NULL;
int inse=0;
if(root == NULL)
root = newnode;
else
while(inse == 0)
{
if(temp->num > newnode->num)
if(temp->left == NULL)
{
temp->left = newnode;
inse = 1;
else
temp = temp->left;
else
{
if(temp->right == NULL)

temp->right = newnode;
inse = 1;
}
else
temp = temp->right;
B. Traversing
Binary search tree can be traversed in three ways.
a. Preorder traversal - traversing binary tree in the order of parent, left and right.
b. In order traversal - traversing binary tree in the order of left, parent and right.
c. Post order traversal - traversing binary tree in the order of left, right and parent.
Algorithms for traversing binary search tree:-
void Preorder(node *t)
1. if (t != NULL)
print t->Num;
if (t->Left != NULL) Preorder(t->Left);
if (t->Right != NULL) Preorder(t->Right);
2. else print “Tree Empty”.
void Inorder(node *t)
1. if (t != NULL)
if (t->Left != NULL) Inorder(t->Left);
print t->Num;
if (t->Right != NULL) Inorder(t->Right);
Void Postorder(node *t)
1. if (t != NULL)
if (t->Left != NULL) Postorder(t->Left);
if (t->Right != NULL) Postorder(t->Right);
print t->Num;

Example:
rootptr
10
6 15
4 8 14 18
7 12 16 19
11 13 17
Preorder traversal - 10, 6, 4, 8, 7, 15, 14, 12, 11, 13, 18, 16, 17, 19
Inorder traversal - 4, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
==> Used to display nodes in ascending order.
Postorder traversal- 4, 7, 8, 6, 11, 13, 12, 14, 17, 16, 19, 18, 15, 10
Traversing implementation
void preorder(node *t){
if(t != NULL){
cout<<t->num<<", ";
if(t->left != NULL)preorder(t->left);
if(t->right != NULL)preorder(t->right);
}
else
cout<<"tree Empty!";
void inorder(node *t){

if(t != NULL){
if(t->left != NULL)inorder(t->left);
cout<<t->num<<", ";
if(t->right != NULL)inorder(t->right);
else

void postorder(node *t){
if(t != NULL){
if(t->left != NULL)postorder(t->left);
if(t->right != NULL)postorder(t->right);
cout<<t->num<<", ";
else

Chapter Three
3. Searching and sorting algorithm

3.1 Introduction to Search Algorithms
• A search algorithm is a method of locating a specific item of information in a larger collection of
data. This section discusses two algorithms for searching the contents of an array.
3.1.1 The Linear Search

• This is a very simple algorithm.
• It uses a loop to sequentially step through an array, starting with the first element.
• It compares each element with the value being searched for and stops when that value is found or
the end of the array is reached.
Implementation linear search

void addbegn(){
node *temp;
temp=new node;
cout<<"Enter Id :";
cin>>temp->id;
cout<<"Enter Age :";
cin>>temp->age;
cout<<"Enter Name :";
cin>>temp->name;
temp->next=NULL;
if(Head == NULL)
Head = temp;
else
temp->next = Head;
Head = temp;
void searchid(){
int k;
cout<<"Enter id you want :"<<endl;
cin>>k;
cout<<"_________________________"<<endl;

node *temp=new node;
if(Head != NULL)
temp=Head;
while(temp != NULL){
if(temp->id == k){
cout<<setw(10)<<"ID"<<setw(14)<<"AGE"<<setw(13)<<"NAME"<<endl;
cout<<setw(10)<<temp->id<<setw(15)<<temp->age<<setw(15)<<temp->name<<endl;
cout<<"__________________________"<<endl;
return;
temp=temp->next;
cout<<"the key is not found!!!!!\n\n";
}
void searchname(){
char k[30];
cout<<"Enter Name You Want :";
cin>>k;
if(Head != NULL)
temp=Head;
while(temp != NULL){
if(strcmp(temp->name,k)==0){
cout<<"__________________________"<<endl;
return;
temp=temp->next;
cout<<"the key is not found!!!!!\n\n";
void display(){
if(Head != NULL){
temp=Head;
cout<<"The Elements Are : "<<endl;
cout<<"_______________________"<<endl;
while(temp != NULL)
cout<<"-------------------------------------------------"<<endl;
temp=temp->next;
cout<<"________________________"<<endl;
else
cout<<"the list is empty!!!\n";
Efficiency of the Linear Search
• The advantage is its simplicity.
– It is easy to understand
– Easy to implement
– Does not require the array to be in order
• The disadvantage is its inefficiency
– If there are 20,000 items in the array and what you are looking for is in the 19,999th
element, you need to search through the entire list.
3.2 Introduction to Sorting Algorithms:

• Sorting algorithms are used to arrange random data into some order
Types of sort algorithm
A. Bubble sort
B. Selection sort
C. Merge sort
D. Quick sort
The Bubble Sort

• An easy way to arrange data in ascending or descending order.
• Bubble sort is a straightforward and simplistic method of sorting data that is used in computer science
education. The algorithm starts at the beginning of the data set. It compares the first two elements, and if
the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements
to the end of the data set. It then starts again with the first two elements, repeating until no swaps have
occurred on the last pass. While simple, this algorithm is highly inefficient and is rarely used except in
education.

Implementation bubble sort

#include<iostream.h>
#include<conio.h>
void sortarray(int [],int);
void showarray(int [],int);
void main()
clrscr();
int values[100],a;
cout<<"Enter The size you want"<<endl;
cin>>a;
for(int i=0;i<a;i++)
cin>>values[i];
}
cout<<"The unsorted values are :"<<endl;
showarray(values,a);
sortarray(values,a);
cout<<"The sorted values are:"<<endl;
getch();
//return 0;
}
void sortarray(int array[], int x)
int swap,temp;
do
swap=0;
for(int i=0;i < (x-1); i++)
if(array[i]>array[i+1])
temp=array[i];
array[i]=array[i+1];
array[i+1]=temp;

swap=1;
}
}
while(swap!=0);
void showarray(int array[],int x)
for(int i=0;i<x;i++)
cout<<array[i]<<" ";
cout<<endl;
Selection Sort
• The bubble sort is inefficient for large arrays because items only move by one element at a time.
• The selection sort moves items immediately to their final position in the array so it makes fewer
exchanges.
• Selection sort is a simple sorting algorithm that improves on the performance of bubble sort. It works by
first finding the smallest element using a linear scan and swapping it into the first position in the list, then
finding the second smallest element by scanning the remaining elements, and so on. Selection sort is unique
compared to almost any other algorithm in that its running time is not affected by the prior ordering of the
list: it performs the same number of operations because of its simple structure. selection sort will usually be
outperformed by insertion sort or the more complicated algorithms.
Implementation of selection sort
#include<conio.h>
void selsortarray(int [],int);
void showarray(int [],int);
void main()
clrscr();
int values[100],a;
cout<<"Enter the size you want"<<endl;
cin>>a;
for(int i=0;i<a;i++)

cin>>values[i];
cout<<"The unsorted values are :"<<endl;

selsortarray(values,a);
cout<<"The sorted values are:"<<endl;
getch();
//return 0;
void selsortarray(int array[], int x)
//int swap,temp;
int startscan,minindex,minvalue;
for(startscan=0;startscan < (x-1); startscan++)
minindex=startscan;
minvalue=array[startscan];
for(int index=startscan+1;index<x;index++)
if(array[index]<minvalue)
{
minvalue=array[index];
minindex=index;
}
array[minindex]=array[startscan];
array[startscan]=minvalue;
void showarray(int array[],int x)

{
for(int i=0;i<x;i++)
cout<<array[i]<<" ";
cout<<endl;

Merge sort
 Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by
comparing every two elements and swapping them if the first should come after the second. It then merges
each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two
lists are merged into the final sorted list.
Implementation of merge sort
// merge sort by asaye hiluf
#include<conio.h>
void mergesort(int[],int,int);
void merge(int[],int,int,int);
void main()
int a[10],p,q,r,i,n;
clrscr();
cout<<"Enter the number of elements";
cin>>n;
p=0;
r=n-1;
cout<<"Enter the array";
for(i=0;i<n;i++)
cin>>a[i];
mergesort(a,p,r);
cout<<"The sorted array is:";
for(i=0;i<n;i++)
cout<<"\n"<<a[i];
getch();
}
void mergesort(int a[],int p,int r)
{
if( p < r)
{ int q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r) ;
merge(a,p,q,r);
}
void merge(int a[],int p,int q,int r)
int c[10];
int i=p;
int j=q+1;
int k=p;
while((i<=q)&&(j<=r))
if(a[i]<a[j])
{
c[k]=a[i];
i=i+1;
k=k+1;
else
{
c[k]=a[j];
j=j+1;
k=k+1;
}
while(i<=q)
c[k] =a[i];
i=i+1;
k=k+1;
}
while(j<=r)
c[k]=a[j];
j=j+1;
k=k+1;
int l=p;
while(l<=r)
a[l]=c[l];
l=l+1;
Quick sort
 Quick sort is a divide and conquer algorithm which relies on a partition operation: to partition an array, we
choose an element, called a pivot, move all smaller elements before the pivot, and move all greater
elements after it. This can be done efficiently in linear time and in-place. We then recursively sort the lesser
and greater sub lists. Efficient implementations of quick sort (with in-place partitioning) are typically
unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice. This makes
quick sort one of the most popular sorting algorithms, available in many standard libraries. The most
complex issue in quick sort is choosing a good pivot element; consistently poor choices of pivots can result
in drastically slower performance.
Implementation of quick sort
//quick sort by asaye hiluf
#include<conio.h>
int Partition(int a[], int beg, int end) //Function to Find Pivot Point
int p=beg, pivot=a[beg], loc;
for(loc=beg+1;loc<=end;loc++)
if(pivot>a[loc])
{
a[p]=a[loc];
a[loc]=a[p+1];
a[p+1]=pivot;
p=p+1;
return p;
void QuickSort(int a[], int beg, int end)

{
if(beg<end)
int p=Partition(a,beg,end); //Calling Procedure to Find Pivot
QuickSort(a,beg,p-1); //Calls Itself (Recursion)
QuickSort(a,p+1,end); //Calls Itself (Recursion)
void main()
clrscr();
int a[100],i,n,beg,end;
cout<<"\n------- QUICK SORT -------\n\n";
cout<<"Enter the No. of Elements : ";
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
beg=1;
end=n;
QuickSort(a,beg,end); //Calling of QuickSort Function
cout<<"\nAfter Sorting : \n";

for(i=1;i<=n;i++)
cout<<a[i]<<endl;
}
getch();

Data Structure Compiled Note

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Data Structure Compiled Note

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structure Compiled Note

Uploaded by

Copyright:

Available Formats

September 1, 2016 Data Structure and Algorithm Analysis

Data Structure and Algorithm Analysis using C++

September 01, 2016

1. Introduction to Data Structures

Basic types of Data Structures

2 Compiled By: Maregu Assefa

An algorithm generally requires space for following components:

Calculating Time Complexity

for(i=0; i < N; i++)

while(low <= high)

4 Compiled By: Maregu Assefa

Types of Notations for Time Complexity

1. Big Oh denotes "fewer than or the same as" <expression> iterations.

3. Big Theta denotes "the same as" <expression> iterations.

4. Little Oh denotes "fewer than" <expression> iterations.

5. Little Omega denotes "more than" <expression> iterations.

Understanding Notations of Time Complexity with Example

5 Compiled By: Maregu Assefa

2. Abstract Data Types (ADTs)

Linear Data Structure:

Non Linear Data Structure:

2.1. Introduction to Linked Lists

Advantages of Linked Lists

6 Compiled By: Maregu Assefa

 Stacks and queues can be easily executed.

Disadvantages of Linked Lists

 The memory is wasted as pointers require extra memory for storage.

Applications of Linked Lists

 Linked lists are used to implement stacks, queues, graphs, etc.

Types of Linked Lists

7 Compiled By: Maregu Assefa

Arrays Vs Linked lists

Singly Linked Lists

8 Compiled By: Maregu Assefa

Creating Linked Lists in C++

Defining the data structure for a linked list

char name[20]; // Name of up to 20 letters

node *next;// Pointer to next node

9 Compiled By: Maregu Assefa

Adding a node to the list

cout<<"Enter Age :";

cout<<"Enter Name :";

10 Compiled By: Maregu Assefa

B. Insert at the end of the list

temp = new node;

cin >> temp->name;

cout << "Please enter the age of the person : ";

cin >> temp->age;

cout << "Please enter the height of the person : ";

cin >> temp->height;

11 Compiled By: Maregu Assefa

while (temp2->next != NULL)

{ temp2 = temp2->next; // Move to next link in chain

{ node *temp, *temp2; // Temporary pointers

// Reserve space for new node and fill it with data

temp = new node;

cout << "Please enter the name of the person: ";

cin >> temp->name;

{ node temp, temp2; // Temporary pointers

{ node temp1, temp2;