Basic Concepts

The term data structure is used to describe the way data is stored, and the term
algorithm is used to describe the way data is processed. Data structures and
algorithms are interrelated. Choosing a data structure affects the kind of algorithm
you might use, and choosing an algorithm affects the data structures we use.

An Algorithm is a finite sequence of instructions, each of which has a clear

meaning and can be performed with a finite amount of effort in a finite length of
time. No matter what the input values may be, an algorithm terminates after
executing a finite number of instructions.

1.1. Introduction to Data Structures:

Data structure is a representation of logical relationship existing between individual elements of

data. In other words, a data structure defines a way of organizing all data items that considers not
only the elements stored but also their relationship to each other. The term data structure is used
to describe the way data is stored.

To develop a program of an algorithm we should select an appropriate data structure for that
algorithm. Therefore, data structure is represented as:

Algorithm + Data structure = Program

A data structure is said to be linear if its elements form a sequence or a linear list. The linear data
structures like an array, stacks, queues and linked lists organize data in linear order. A data
structure is said to be non linear if its elements form a hierarchical classification where, data
items appear at various levels.

Trees and Graphs are widely used non-linear data structures. Tree and graph structures represents
hierarchial relationship between individual data elements. Graphs are nothing but trees with
certain restrictions removed.

Data structures are divided into two types:

 Primitive data structures.

 Non-primitive data structures.

Primitive Data Structures are the basic data structures that directly operate upon the machine
instructions. They have different representations on different computers. Integers, floating point
numbers, character constants, string constants and pointers come under this category.

Non-primitive data structures are more complicated data structures and are derived from
primitive data structures. They emphasize on grouping same or different data items with
relationship between each data item. Arrays, lists and files come under this category. Figure
1.1 shows the classification of data structures.
 Fig ure 1. 1. C lass if icat io n of Da t a St ruct ures

1.2. Data structures: Organization of data

The collection of data you work with in a program have some kind of structure or organization.
No matter how complex your data structures are they can be broken down into two fundamental
types:
 Contiguous
 Non-Contiguous.

In contiguous structures, terms of data are kept together in memory (either RAM or in a file). An
array is an example of a contiguous structure. Since each element in the array is located next to
one or two other elements. In contrast, items in a non-contiguous structure and scattered in
memory, but we linked to each other in some way. A linked list is an example of a non-contiguous
data structure. Here, the nodes of the list are linked together using pointers stored in each node.
Figure 1.2 below illustrates the difference between contiguous and non- contiguous structures.

1 2 3

Figure 1.2 Contiguous and Non-contiguous structures compared

Contiguous structures:

Contiguous structures can be broken drawn further into two kinds: those that contain data items
of all the same size, and those where the size may differ. Figure 1.2 shows example of each kind.
The first kind is called the array. Figure 1.3(a) shows an example of an array of numbers. In an
array, each element is of the same type, and thus has the same size.

The second kind of contiguous structure is called structure, figure 1.3(b) shows a simple structure
consisting of a person’s name and age. In a struct, elements may be of different data types and
thus may have different sizes.
 For example, a person’s age can be represented with a simple integer that occupies two bytes of
memory. But his or her name, represented as a string of characters, may require many bytes and
may even be of varying length.

Couples with the atomic types (that is, the single data-item built-in types such as integer, float
and pointers), arrays and structs provide all the “mortar” you need to built more exotic form of
data structure, including the non-contiguous forms.

int arr[3] = {1, 2, 3}; struct cust_data

1 2 3 {
int age;
char name[20];
};

cust_data bill= {21, “bill the student”};

(a) Array
21
(b) struct

“bill the student”

Figure 1.3 Examples of contiguous structures.

Non-contiguous structures:

Non-contiguous structures are implemented as a collection of data-items, called nodes, where

each node can point to one or more other nodes in the collection. The simplest kind of non-
contiguous structure is linked list.

A linked list represents a linear, one-dimension type of non-contiguous structure, where there is
only the notation of backwards and forwards. A tree such as shown in figure 1.4(b) is an example
of a two-dimensional non-contiguous structure. Here, there is the notion of up and down and left
and right.

In a tree each node has only one link that leads into the node and links can only go down the tree.
The most general type of non-contiguous structure, called a graph has no such restrictions. Figure
1.4(c) is an example of a graph.

A B A
B
D
A

B
F
D F

Figure 1.4. Examples of non-contiguous structures

Hybrid structures:

If two basic types of structures are mixed then it is a hybrid form. Then one part contiguous and
another part non-contiguous. For example, figure 1.5 shows how to implement a double– linked
list using three parallel arrays, possibly stored a past from each other in memory.

A B C

D P N

1
A 3 4
2
B 4 0
3
C 0 1
4
D 1 2

Figure 1.5. A double linked list via a hybrid data structure

The array D contains the data for the list, whereas the array P and N hold the previous and next
“pointers’’. The pointers are actually nothing more than indexes into the D array. For instance,
D[i] holds the data for node i and p[i] holds the index to the node previous to i, where may or
may not reside at position i–1. Like wise, N[i] holds the index to the next node in the list.

1.3. Abstract Data Type (ADT):

The design of a data structure involves more than just its organization. You also need to plan for
the way the data will be accessed and processed – that is, how the data will be interpreted actually,
non-contiguous structures – including lists, tree and graphs – can be implemented either
contiguously or non- contiguously likewise, the structures that are normally treated as
contiguously - arrays and structures – can also be implemented non-contiguously.

The notion of a data structure in the abstract needs to be treated differently from whatever is used
to implement the structure. The abstract notion of a data structure is defined in terms of the
operations we plan to perform on the data.

Considering both the organization of data and the expected operations on the data, leads to the
notion of an abstract data type. An abstract data type in a theoretical construct that consists of
data as well as the operations to be performed on the data while hiding implementation.

For example, a stack is a typical abstract data type. Items stored in a stack can only be added and
removed in certain order – the last item added is the first item removed. We call these operations,
pushing and popping. In this definition, we haven’t specified have items are stored on the stack,
or how the items are pushed and popped. We have only specified the valid operations that can be
performed.
 For example, if we want to read a file, we wrote the code to read the physical file device. That
is, we may have to write the same code over and over again. So we created what is know
today as an ADT. We wrote the code to read a file and placed it in a library for a programmer to
use.

As another example, the code to read from a keyboard is an ADT. It has a data structure, character
and set of operations that can be used to read that data structure.

To be made useful, an abstract data type (such as stack) has to be implemented and this is where
data structure comes into ply. For instance, we might choose the simple data structure of an array
to represent the stack, and then define the appropriate indexing operations to perform pushing
and popping.

1.4. Selecting a data structure to match the operation:

The most important process in designing a problem involves choosing which data structure to
use. The choice depends greatly on the type of operations you wish to perform.

Suppose we have an application that uses a sequence of objects, where one of the main operations
is delete an object from the middle of the sequence. The code for this is as follows:
void delete (int *seg, int &n, int posn)
// delete the item at position from an array of n elements.
{
if (n)
{
int i=posn;
n--;
while (i < n)
{
seq[i] = seg[i+1]; i++;
}
}
return;
}

This function shifts towards the front all elements that follow the element at position posn. This
shifting involves data movement that, for integer elements, which is too costly. However, suppose
the array stores larger objects, and lots of them. In this case, the overhead for moving data
becomes high. The problem is that, in a contiguous structure, such as an array the logical ordering
(the ordering that we wish to interpret our elements to have) is the same as the physical ordering
(the ordering that the elements actually have in memory).

If we choose non-contiguous representation, however we can separate the logical ordering from
the physical ordering and thus change one without affecting the other. For example, if we store
our collection of elements using a double–linked list (with previous and next pointers), we can
do the deletion without moving the elements, instead, we just modify the pointers in each node.
The code using double linked list is as follows:

void delete (node * beg, int posn)

//delete the item at posn from a list of elements.
{
int i = posn;
node *q = beg;
while (i && q)
{

i--;
q=q next;
}

if (q)
{ /* not at end of list, so detach P by making previous and
next nodes point to each other */
node *p = q -> prev;
node *n = q -> next; if
(p)
p -> next = n;
if (n)
n -> prev = P;
}
return;
}
The process of detecting a node from a list is independent of the type of data stored in the node,
and can be accomplished with some pointer manipulation as illustrated in figure below:

A
C

A A

Figure 1.6 Detaching a node from a list

Since very little data is moved during this process, the deletion using linked lists will often be
faster than when arrays are used.

It may seem that linked lists are superior to arrays. But is that always true? There are trade offs.
Our linked lists yield faster deletions, but they take up more space because they require two extra
pointers per element.

1.5. Algorithm

An algorithm is a finite sequence of instructions, each of which has a clear meaning and can be
performed with a finite amount of effort in a finite length of time. No matter what the input values
may be, an algorithm terminates after executing a finite number of instructions. In addition every
algorithm must satisfy the following criteria:

Input: there are zero or more quantities, which are externally supplied;

Output: at least one quantity is produced;

Definiteness: each instruction must be clear and unambiguous;

Finiteness: if we trace out the instructions of an algorithm, then for all cases the algorithm will
terminate after a finite number of steps;

Effectiveness: every instruction must be sufficiently basic that it can in principle be carried out
by a person using only pencil and paper. It is not enough that each operation be definite, but it
must also be feasible.

In formal computer science, one distinguishes between an algorithm, and a program. A program
does not necessarily satisfy the fourth condition. One important example of such a program for
a computer is its operating system, which never terminates (except for system crashes) but
continues in a wait loop until more jobs are entered.

We represent an algorithm using pseudo language that is a combination of the constructs of a

programming language together with informal English statements.

1.6. Practical Algorithm design issues:

Choosing an efficient algorithm or data structure is just one part of the design process. Next, will
look at some design issues that are broader in scope. There are three basic design goals that we
should strive for in a program:
1. Try to save time (Time complexity).
2. Try to save space (Space complexity).
3. Try to have face.

A program that runs faster is a better program, so saving time is an obvious goal. Like wise, a
program that saves space over a competing program is considered desirable. We want to “save
face” by preventing the program from locking up or generating reams of garbled data.

1.7. Performance of a program:

The performance of a program is the amount of computer memory and time needed to run a
program. We use two approaches to determine the performance of a program. One is analytical,
and the other experimental. In performance analysis we use analytical methods, while in
performance measurement we conduct experiments.

Time Complexity:

The time needed by an algorithm expressed as a function of the size of a problem is called the
TIME COMPLEXITY of the algorithm. The time complexity of a program is the amount of
computer time it needs to run to completion.

The limiting behavior of the complexity as size increases is called the asymptotic time complexity.
It is the asymptotic complexity of an algorithm, which ultimately determines the size of problems
that can be solved by the algorithm.

Space Complexity:

The space complexity of a program is the amount of memory it needs to run to completion. The
space need by a program has the following components:
Instruction space: Instruction space is the space needed to store the compiled version of the
program instructions.

Data space: Data space is the space needed to store all constant and variable values. Data space
has two components:
 Space needed by constants and simple variables in program.
 Space needed by dynamically allocated objects such as arrays and class instances.
Environment stack space: The environment stack is used to save information needed to
resume execution of partially completed functions.

Instruction Space: The amount of instructions space that is needed depends on factors such as:
 The compiler used to complete the program into machine code.
 The compiler options in effect at the time of compilation
 The target computer.

1.8. Classification of Algorithms

If ‘n’ is the number of data items to be processed or degree of polynomial or the size of the file
to be sorted or searched or the number of nodes in a graph etc.

1 Next instructions of most programs are executed once or at most only a few times. If
all the instructions of a program have this property, we say that its running time is a
constant.

Log n When the running time of a program is logarithmic, the program gets slightly slower
as n grows. This running time commonly occurs in programs that solve a big problem
by transforming it into a smaller problem, cutting the size by some constant fraction.,
When n is a million, log n is a doubled whenever n doubles, log n increases by a
constant, but log n does not double until n increases to n2.

n When the running time of a program is linear, it is generally the case that a small
amount of processing is done on each input element. This is the optimal situation for
an algorithm that must process n inputs.

n. log n This running time arises for algorithms but solve a problem by breaking it up into smaller
sub-problems, solving them independently, and then combining the solutions. When
n doubles, the running time more than doubles.

n2 When the running time of an algorithm is quadratic, it is practical for use only on
relatively small problems. Quadratic running times typically arise in algorithms that
process all pairs of data items (perhaps in a double nested loop) whenever n doubles,
the running time increases four fold.

n3 Similarly, an algorithm that process triples of data items (perhaps in a triple– nested
loop) has a cubic running time and is practical for use only on small problems.
Whenever n doubles, the running time increases eight fold.

2n Few algorithms with exponential running time are likely to be appropriate for
practical use, such algorithms arise naturally as “brute–force” solutions to problems.
Whenever n doubles, the running time squares.
 1.9. Complexity of Algorithms

The complexity of an algorithm M is the function f(n) which gives the running time and/or
storage space requirement of the algorithm in terms of the size ‘n’ of the input data. Mostly,
the storage space required by an algorithm is simply a multiple of the data size ‘n’. Complexity
shall refer to the running time of the algorithm.

The function f(n), gives the running time of an algorithm, depends not only on the size ‘n’ of the
input data but also on the particular data. The complexity function f(n) for certain cases are:

1. Best Case : The minimum possible value of f(n) is called the best case.
2. Average Case : The expected value of f(n).
3. Worst Case : The maximum value of f(n) for any key possible input.

The field of computer science, which studies efficiency of algorithms, is known as analysis
of algorithms.

Algorithms can be evaluated by a variety of criteria. Most often we shall be interested in the
rate of growth of the time or space required to solve larger and larger instances of a problem.
We will associate with the problem an integer, called the size of the problem, which is a
measure of the quantity of input data.

BIG O NOTATION

Big O notation is a mathematical tool used in computer science to describe the efficiency of an
algorithm by analyzing its worst-case time or space complexity as input () grows. It focuses on
the asymptotic growth rate—how runtime increases relative to input size—rather than exact
measurements, with common notation including (constant), (linear), and (quadratic).

Key Aspects of Big O Notation

 Purpose: It helps compare algorithms, determining which is faster or more efficient as the
dataset becomes large.

 Worst-Case Focus:

It defines the maximum time or space required (upper bound)

 Complexity Types: It describes time complexity (how fast it runs) and space complexity (how
much memory it uses).

 Simplification: It ignores constant factors and lower-order terms to focus on the highest-order
growth rate.

Time Complexities in Big O

O(1) – Constant Time Complexity

O(1) complexity, also known as “constant execution time,” is highly desirable in algorithms and
operations, as it means that the time required to operate does not increase as the size of the input
data increases. A very well-known example of a data structure with O(1) time complexity is
arrays, where O(1) complexity is achieved by accessing an array element through its index.
This means that no matter how big the array is, the time required to access a specific element is
the same as direct access to the element. It’s done in a constant step of time.

int[] array = new int[] { 10, 20, 30, 40, 50 };

int element = array[2];
[Link]($"Element at index 2: {element}");
The code above defines an array with some elements, then finds the value existing in the second
index of the array and prints the response, where only one execution step is required, which
means the function is in constant time with time complexity O(1).

In other words, whenever the search for an element occurs through the index, the search will be
instantaneous, in constant time

O(log n) – Logarithmic Time Complexity

Logarithmic time complexity, represented by O(log n), is a common characteristic of efficient

algorithms in which the execution time increases logarithmically with the size of the input (n).
Logarithmic time complexity means that the running time of the algorithm increases
proportionally to the logarithm of the input size.

This means that even with a substantial increase in input size, the algorithm’s running time will
increase much more slowly compared to algorithms that have linear or quadratic complexity.

O(n) – Linear Time Complexity

Linear time complexity, represented by O(n), is common in algorithms where the execution time
increases linearly with the size of the input. That is, as the size of the input increases, the
execution time also increases accordingly.

A common example of an algorithm with linear, O(n) time complexity is the sequential search
also known as simple search, which runs on an unordered list. To implement a sequential search,
simply create an unordered list and have a target, then go through each item in the list and check
at each iteration if the sought target is equal to the current element.

O(n log n) – Log-Linear Time Complexity

The time complexity O(n log n) indicates an intermediate growth between linear (O(n)) and
quadratic (O(n²)). It is common in algorithms that divide the problem into smaller parts and
perform logarithmic operations on each part, followed by a linear operation that combines these
parts.

Algorithms with O(n log n) time complexity are often found in sorting algorithms and in
problems involving divide and conquer.

A common example of an algorithm with O(n log n) time complexity is QuickSort. QuickSort is
commonly used to sort a collection of elements in ascending or descending order.
O(n²) – Quadratic Time Complexity

O(n²) refers to the quadratic time complexity of an algorithm, where the execution time increases
squarely with the input size. This means that if the input size increases, the algorithm’s running
time increases by the square of that size.

This time complexity is common in algorithms that contain two nested loops, where each loop
runs within an order of magnitude of n and both loops execute n times. As a result, the total
execution time becomes proportional to n².

A common example with O(n²) time complexity is BubbleSort. In BubbleSort, adjacent elements
are compared and swapped repeatedly until the array is sorted. This algorithm has O(n²) time
complexity in the worst case, as it requires each element to be compared and possibly swapped
with each other element.

Array

An array is a group of similar elements or data items of the same type collected at contiguous
memory locations. In simple words, we can say that in computer programming, arrays are
generally used to organize the same type of data.

Array for Integral value:

Array for Character value:

Representation of an Array:
Arrays can be represented in several ways, depending on the different languages. To make you
understand, we can take one example of the C language. The picture below shows the
representation of the array.

Arrays always store the same type of values. In the above example:

 int is a type of data value.

 Data items stored in an array are known as elements.
 The location or placing of each element has an index value.
Important: Array can store only the same type of data items. From the below example you can
see how it works:

 In the array a, we have stored all integral values (same type)

 In the array b, we have stored all char values (same type)
 In the array c, there is integral, float, char all types of values and this is not something an
array can store so, option 3 is wrong because an array cannot store different types of
values.

Declaration Syntax of Array:

VariableType VariableName[Sequence of Elements];

Example 1: For integral value

int A[10];

Here 10 means, this array A can have 10 integer elements.

2 5 8 44 21 11 7 9 3 1

Example 2: For character value

char B[10];

This array B can have 10 character elements.

f d a b n j l s e y

Initialization of an Array:

If an array is described inside a function, the elements will have garbage value. And in case an
array is static or global, its elements will be initialized automatically to 0.

We can say that we can simply initialize elements of an array at the time of declaration and for
that, we have to use the proper syntax:

Syntax: datatype Array_Name[size] = { value1, value2, value3, ….. valueN };

Types of Arrays:

There are two types of arrays:

 One-Dimensional Arrays
 Multi-Dimensional Arrays

One -Dimensional Arrays

A one-dimensional array is a kind of linear array. It involves single sub-scripting. The []

(brackets) is used for the subscript of the array and to declare and access the elements from the
array.

Syntax: DataType ArrayName [size];

For example: int a[10];

Multi-Dimensional Arrays

In multi-dimensional arrays, we have two categories:

 Two-Dimensional Arrays
 Three-Dimensional Arrays
1. Two-Dimensional Arrays
An array involving two subscripts [] [] is known as a two-dimensional array. They are also
known as the array of the array. Two-dimensional arrays are divided into rows and columns and
are able to handle the data of the table.

Syntax: DataType ArrayName[row_size][column_size];

For Example: int arr[5][5];

2. Three-Dimensional Arrays

When we require to create two or more tables of the elements to declare the array elements, then
in such a situation we use three-dimensional arrays.

Syntax: DataType ArrayName[size1][size2][size3];

For Example: int a[5][5][5];

Advantages of Array

 It is a better version of storing the data of the same size and same type.
 It enables us to collect the number of elements in it.
 Arrays have a safer cache positioning that improves performance.
 Arrays can represent multiple data items of the same type using a single name.

Disadvantages Of Array:

 In an array, it is essential to identify the number of elements to be stored.

 It is a static structure. It means that in an array, the memory size is fixed.
 When it comes to insertion and deletion, it is a bit difficult because the elements are
stored sequentially and the shifting operation is expensive.\

STRINGS REPRESENTATION

String is a linear data structure and it is also known as the character array ( array of characters).
We are sequentially storing characters in the string like the way we are doing in the integer
arrays. String data structure is having a null character ‘\0’ that terminates the entire string in data
structure.

Here is the pictorial representation for understanding string in data structure and the working of
it:
REPRESENTATION OF STRING IN DATA STRUCTURE
Representation of string in data structures in memory is the representation of an array of
characters. For every character in the array there is a unique index associated with it.

Unique indices help to access characters from the string so we can perform multiple operations
on it like modification, searching of character, deletion of character in the string and
concatenation as well.

Example: “Hello “itself is a string that consists of 5 characters.

String Operations

There are different operations we can perform in a data structure along with an examples:

Insertion Operation

Inserting characters in a given string name str_iskills at a specified position.

Example: char str_data [ 15] = “data structur”

In this example I want to insert an element (or character) at the last index ‘13’. Let’s take a
character ‘e’ that we need to add in the original character string, the respective output of the
operation is specified below.

Char str_data [ 15] =” data structure”;

‘e’ is added at the end of the character array which is required to add at the specified index.

Access Operation

Access operation in string is used to access a particular character of a string by referring to the
index number.

Example: char arr_data [ 15] = “data structure”;

If i want to access ‘s ‘from the string, then we have to specify it to the index number to find or
access the character from the string.
 Deletion Operation

Deletion operation in a string is used to delete the particular character from the string (array of
characters).

Example: char arr_data [ 16] = “datas structure “;

Here in this example I want to delete the ‘s’ from the datas. In this case i have to use the delete
operation to remove the extra character from the string.

The final output for the deletion operation specified below:

char arr_data [ 16] = “data structure”;

Concatenation Operation

Concatenation operation performed on the string to join the string together. If we take a real life
application that we want to show or display the full name of a person, then in this case we have
to concatenate the first name and the last name of a person to get the full name.

Example: char arr_string1 [ 6] = “data”;

char arr_string2 [9] =” structure”;

We need to join both the strings arr_string1 and arr_string2 while performing concatenation
operations.

Specified output: char output_string [ 15] = “data structure”;

( “data structure” ) specified output of the concatenated string.

Applications
Strings are fundamental to numerous applications in computer science:
 Text processing and editing: Core component of text editors and word processors.

 Natural Language Processing (NLP): Used for analyzing and manipulating human language
data.

 Data representation: Used to store data in formats like JSON, XML, and CSV.

 Security and validation: Essential for validating user input (e.g., email addresses, phone
numbers) to prevent security vulnerabilities like SQL injection or buffer overflows.

 Networking and databases: Used for network communication (e.g., HTTP requests) and storing
text-based data in databases.

 Bioinformatics: Used in DNA sequencing and pattern matching algorithms.

 MATRICES/MATRIX

A matrix is a two-dimensional data structure, where we can store data in rows and columns
format. In data structures, a matrix is a two-dimensional array of elements, with the same data
type. All values in a matrix must have the same data type. The matrix can have a fixed number of
rows and columns, or it can be dynamically allocated based on the requirement.

MATRICES OPERATION

There are various operations that can be performed on matrices. Some of the common operations
are:

Traversal - Traversing a matrix means visiting each element in the matrix exactly once. This can
be done using nested loops to iterate over each row and column in the matrix.

Search - Searching for an element in a matrix involves finding the position of a specific element
in the matrix. This can be done by traversing the matrix and comparing each element with the
target element.

Row-wise Traversal - Traversing a matrix row-wise means visiting each element in each row of
the matrix. This can be done by iterating over each row and then iterating over each column in
the row.

Column-wise Traversal - Traversing a matrix column-wise means visiting each element in each
column of the matrix. This can be done by iterating over each column and then iterating over
each row in the column.

Accessing Elements - Accessing an element in a matrix means retrieving the value stored at a
specific position in the matrix. This can be done by specifying the row and column index of the
element to be accessed.

Applications OF Matrices
 Graphics: Representing images or 3D transformations.

 Mathematics/Physics: Solving linear equations and modeling systems.

 Data Analysis: Storing and organizing structured data.

LINKED LISTS

Linked lists and arrays are similar since they both store collections of data. Array is the most
common data structure used to store collections of elements.
A linked list is a non-sequential collection of data items. It is a dynamic data structure. For
every data item in a linked list, there is an associated pointer that would give the memory
location of the next data item in the linked list.

The data items in the linked list are not in consecutive memory locations. They may be
anywhere, but the accessing of these data items is easier as each data item contains the address
of the next data item.

Advantages of linked lists:

Linked lists have many advantages. Some of the very important advantages are:

1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the
execution of a program.
2. Linked lists have efficient memory utilization. Here, memory is not pre- allocated.
Memory is allocated whenever it is required and it is de-allocated (removed) when
it is no longer needed.
3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in
inserting a data item at a specified position and deletion of the data item from the
given position.
4. Many complex applications can be easily carried out with linked lists.

Disadvantages of linked lists:

1. It consumes more space because every node requires a additional pointer to store
address of the next node.
2. Searching a particular element in list is difficult and also time consuming.

Types of Linked Lists:

Basically we can put linked lists into the following four items:

[Link] Linked List.

[Link] Linked List.
[Link] Linked List.
[Link] Double Linked List.

A single linked list is one in which all nodes are linked together in some sequential manner.
Hence, it is also called as linear linked list.
A double linked list is one in which all nodes are linked together by multiple links which
helps in accessing both the successor node (next node) and predecessor node (previous node)
from any arbitrary node within the list. Therefore, each node in a double linked list has two
link fields (pointers) to point to the left node (previous) and the right node (next). This helps to
traverse in forward direction and backward direction.

A circular linked list is one, which has no beginning and no end. A single linked list can be
made a circular linked list by simply storing address of the very first node in the link field of
the last node.

A circular double linked list is one, which has both the successor pointer and predecessor
pointer in the circular manner.

Comparison between array and linked list:

ARRAY LINKED LIST

Size of an array is fixed Size of a list is not fixed

Memory is allocated from stack Memory is allocated from heap

It is necessary to specify the number of It is not necessary to specify the number of
elements during declaration (i.e., during elements during declaration (i.e., memory
compile time). is allocated during run
time).
It occupies less memory than a linked list It occupies more memory.
for the same number of elements.
Inserting new elements at the front is Inserting a new element at any position can
potentially expensive because existing be carried out easily.
elements need to be shifted over to make
room.
Deleting an element from an array is not Deleting an element is possible.
possible.

3.5. Array based linked lists:

Another alternative is to allocate the nodes in blocks. In fact, if you know the maximum size
of a list a head of time, you can pre-allocate the nodes in a single array. The result is a hybrid
structure – an array based linked list. Figure 3.5.1 shows an example of null terminated single
linked list where all the nodes are allocated contiguously in an array.

300
 Figure 3.5.1. An array based linked list

3.6. Double Linked List:

A double linked list is a two-way list in which all nodes will have two links. This helps in
accessing both successor node and predecessor node from the given node position. It provides
bi-directional traversing. Each node contains three fields:

 Left link.
 Data.
 Right link.

The left link points to the predecessor node and the right link points to the successor node.
The data field stores the required data.

Many applications require searching forward and backward thru nodes of a list. For
example, searching for a name in a telephone directory would need forward and backward
scanning thru a region of the whole list.

The basic operations in a double linked list are:

 Creation.
 Insertion.
 Deletion.
 Traversing.
A double linked list is shown in figure 3.3.1.

100 20 300

Figure 3.3.1. Double Linked List

The beginning of the double linked list is stored in a "start" pointer which points to the first
node. The first node’s left link and last node’s right link is set to NULL.

The following code gives the structure definition:

struct dlinklist
{ left data right
struct dlinklist *left;
int data;
struct dlinklist *right;

};

typedef struct dlinklist node;

node *start = NULL;

Figure 3.4.1. Structure definition, double link node and empty list

Creating a node for Double Linked List:

Creating a double linked list starts with creating a node. Sufficient memory has to be allocated
for creating a node. The information is stored in the memory, allocated by using the malloc()
function. The function getnode(), is used for creating a node, after allocating memory for the
structure of type node, the information for the item (i.e., data) has to be read from the user and
set left field to NULL and right field also set to NULL (see figure 3.2.2).

node* getnode()
{
node* newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter data: "); X 10 X
scanf("%d", &newnode -> data);
newnode -> left = NULL;
newnode -> right = NULL;
return newnode;
}
Figure 3.4.2. new node with a value of 10
Creating a Double Linked List with ‘n’ number of nodes:

The following steps are to be followed to create ‘n’ number of nodes:

 Get the new node using getnode().

newnode =getnode();

 If the list is empty then start = newnode.

 If the list is not empty, follow the steps given below:

 The left field of the new node is made to point the previous node.

 The previous nodes right field must be assigned with address of the
new node.

 Repeat the above steps ‘n’ times.

Figure 3.4.3 shows 3 items in a double linked list stored at different locations.

100 20 300

Figure 3.4.3. Double Linked List with 3 nodes

 X 100 20 300

Figure 3.4.5. Inserting a node at the end

Inserting a node at an intermediate position:

The following steps are followed, to insert a new node in an intermediate position in the list:

 Get the new node using getnode().

newnode=getnode();

 Ensure that the specified position is in between first node and last node. If not,
specified position is invalid. This is done by countnode() function.

 Store the starting address (which is in start pointer) in temp and prev pointers. Then
traverse the temp pointer upto the specified position followed by prev pointer.

 After reaching the specified position, follow the steps given below:

newnode -> left = temp;

newnode -> right = temp -> right; temp
-> right -> left = newnode; temp ->
right = newnode;

The function dbl_insert_mid(), is used for inserting a node in the intermediate position. Figure
3.4.6 shows inserting a node into the double linked list at a specified intermediate position
other than beginning and end.

start X 10 400
100 40 200
100
400
400 20 300
200
100

200 30 X
300
Figure 3.4.6. Inserting a node at an intermediate position
Deleting a node at the beginning:

The following steps are followed, to delete a node at the beginning of the list:

 If list is empty then display ‘Empty List’ message.

 If the list is not empty, follow the steps given below:

temp = start;
start = start -> right; start -
> left = NULL; free(temp);

The function dbl_delete_beg(), is used for deleting the first node in the list. Figure
3.4.6 shows deleting a node at the beginning of a double linked list.

Figure 3.4.6. Deleting a node at beginning

Deleting a node at the end:

The following steps are followed to delete a node at the end of the list:
 If list is empty then display ‘Empty List’ message

 If the list is not empty, follow the steps given below:

temp = start;
while(temp -> right != NULL)
{
temp = temp -> right;
}
temp -> left -> right = NULL;
free(temp);

The function dbl_delete_last(), is used for deleting the last node in the list. Figure 3.4.7 shows
deleting a node at the end of a double linked list.

Figure 3.4.7. Deleting a node at the end

3.7. Circular Single Linked List:

It is just a single linked list in which the link field of the last node points back to the address
of the first node. A circular linked list has no beginning and no end. It is necessary to establish a
special pointer called start pointer always pointing to the first node of the list. Circular linked
lists are frequently used instead of ordinary linked list because many operations are much
easier to implement. In circular linked list no null pointers are used, hence all pointers contain
valid address.

A circular single linked list is shown in figure 3.6.1.

Figure 3.6.1. Circular Single Linked List

The basic operations in a circular single linked list are:

 Creation.
 Insertion.
 Deletion.
 Traversing.

Creating a circular single Linked List with ‘n’ number of nodes:

The following steps are to be followed to create ‘n’ number of nodes:

 Get the new node using getnode().

newnode = getnode();

 If the list is empty, assign new node as start.

start = newnode;

 If the list is not empty, follow the steps given below:

temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;

 Repeat the above steps ‘n’ times.

 newnode -> next = start;

The function createlist(), is used to create ‘n’ number of nodes:

Inserting a node at the beginning:

The following steps are to be followed to insert a new node at the beginning of the circular
list:

 Get the new node using getnode().

newnode = getnode();

 If the list is empty, assign new node as start.

start = newnode; newnode

-> next = start;

 If the list is not empty, follow the steps given below:

last = start;
while(last -> next != start) last
= last -> next;
newnode -> next = start; start =
newnode;
last -> next = start;
The function cll_insert_beg(), is used for inserting a node at the beginning. Figure
3.6.2 shows inserting a node into the circular single linked list at the beginning.

Figure 3.6.2. Inserting a node at the beginning

Inserting a node at the end:

The following steps are followed to insert a new node at the end of the list:

 Get the new node using getnode().

newnode = getnode();

 If the list is empty, assign new node as start.

start = newnode; newnode

-> next = start;

 If the list is not empty follow the steps given below:

temp = start;
while(temp -> next != start)
temp = temp -> next;
temp -> next = newnode;
newnode -> next = start;

The function cll_insert_end(), is used for inserting a node at the end.

Figure 3.6.3 shows inserting a node into the circular single linked list at the end.

Figure 3.6.3 Inserting a node at the end.

Deleting a node at the beginning:

The following steps are followed, to delete a node at the beginning of the list:

 If the list is empty, display a message ‘Empty List’.

 If the list is not empty, follow the steps given below:

last = temp = start; while(last -

> next != start)
last = last -> next; start
= start -> next;
last -> next = start;

 After deleting the node, if the list is empty then start = NULL.

The function cll_delete_beg(), is used for deleting the first node in the list. Figure 3.6.4 shows
deleting a node at the beginning of a circular single linked list.

Figure 3.6.4. Deleting a node at beginning.

Deleting a node at the end:

The following steps are followed to delete a node at the end of the list:

 If the list is empty, display a message ‘Empty List’.

 If the list is not empty, follow the steps given below:

temp = start; prev

= start;
while(temp -> next != start)
{
prev = temp;
temp = temp -> next;
}
prev -> next = start;

 After deleting the node, if the list is empty then start = NULL.

The function cll_delete_last(), is used for deleting the last node in the list.
}

3.8. Circular Double Linked List:

A circular double linked list has both successor pointer and predecessor pointer in circular
manner. The objective behind considering circular double linked list is to simplify the
insertion and deletion operations performed on double linked list. In circular double linked list
the right link of the right most node points back to the start node and left link of the first node
points to the last node. A circular double linked list is shown in figure 3.8.1.

Figure 3.8.1. Circular Double Linked List

The basic operations in a circular double linked list are:

 Creation.
 Insertion.
 Deletion.
 Traversing.
Creating a Circular Double Linked List with ‘n’ number of nodes:

The following steps are to be followed to create ‘n’ number of nodes:

 Get the new node using getnode().

newnode = getnode();

 If the list is empty, then do the following

start = newnode;
newnode -> left = start;
newnode ->right = start;

 If the list is not empty, follow the steps given below:

newnode -> left = start -> left;
newnode -> right = start;
start -> left->right = newnode; start -
> left = newnode;

 Repeat the above steps ‘n’ times.

The function cdll_createlist(), is used to create ‘n’ number of nodes:

Inserting a node at the beginning:

The following steps are to be followed to insert a new node at the beginning of the list:

 Get the new node using getnode().

newnode=getnode();

 If the list is empty, then

start = newnode; newnode
-> left = start; newnode ->
right = start;

 If the list is not empty, follow the steps given below:

newnode -> left = start -> left;
newnode -> right = start;
start -> left -> right = newnode; start ->
left = newnode;
start = newnode;

The function cdll_insert_beg(), is used for inserting a node at the beginning. Figure
3.8.2 shows inserting a node into the circular double linked list at the beginning.

start

400

400 10 200 100 20 300 200 30 400

100 200 300

300 40 100

400

Figure 3.8.2. Inserting a node at the beginning

Inserting a node at the end:

The following steps are followed to insert a new node at the end of the list:

 Get the new node using getnode()

newnode=getnode();

 If the list is empty, then

start = newnode; newnode
-> left = start; newnode ->
right = start;

 If the list is not empty follow the steps given below:

newnode -> left = start -> left;
newnode -> right = start;
start -> left -> right = newnode; start ->
left = newnode;

The function cdll_insert_end(), is used for inserting a node at the end. Figure 3.8.3
shows inserting a node into the circular linked list at the end.
start

100

400 10 200 100 20 300 200 30 400

100 200 300

300 40 100

400

Figure 3.8.3. Inserting a node at the end

Inserting a node at an intermediate position:

The following steps are followed, to insert a new node in an intermediate position in the list:

 Get the new node using getnode().

newnode=getnode();

 Ensure that the specified position is in between first node and last node. If not,
specified position is invalid. This is done by countnode() function.

 Store the starting address (which is in start pointer) in temp. Then traverse the
temp pointer upto the specified position.

 After reaching the specified position, follow the steps given below:
newnode -> left = temp;
newnode -> right = temp -> right; temp
-> right -> left = newnode; temp ->
right = newnode; nodectr++;