Unit 1 – Introduction

 Structure:
1.0 Introduction
1.1 Unit Objectives
1.2 Concept of Data type
1.3 Data structures
1.4 Abstract Data types
1.5 Summary
1.6 Key Terms
1.7 Check Your Progress

1.0 Introduction:
All computer programs involve operations on data. Data plays an important role in programming.
The data may be defined as a value or a set of values, such as the name and age of a person, the grade of a
student, the salary of an employee, and so on. It is just a collection of values and no conclusion can be drawn from
it. However, after processing, it becomes information that can help in making decisions. In order to process data, it
should be available in the main memory since the processor can only act on data in the main memory. In order to
represent the data in the main memory, some model is needed to process it efficiently. This model is called a data
structure. Various models are available, and this unit will introduce you to these various structures and the different
operations that can be performed on them.

1.1 Unit Objectives:

After going through this unit, the reader will be able to:
 Understand the basic concept of data type
 Explain the different types of data structures
 Describe the abstract data types

1.2 Concept of Data type:

Data is a value or a collection of values that may be obtained from an experiment, survey,
etc. The term which is used to refer to a single unit of values is called a data item. A data item may be a group item
or an elementary item. A group item is the one that can be further divided into sub-items, whereas an elementary
item is the one that cannot be divided further. The address of a person, for example, is a group item because it is
usually divided into sub-items like house number, street, city, state, PIN code, etc. On the other hand, the state, city,
PIN code, etc., are elementary items. A set of data items are used to represent a thing in the real world with the
physical or the logical existence called an entity. In the context of entities, the data items are termed as attributes or
properties of the entity. The attributes like name, roll number, marks, and so on, for example, can be used to
represent an entity student. Generally, each attribute of an entity is assigned a particular value, such as the name is
assigned a value ‘James’. A set of entities having similar attributes is called an entity set. e.g.: all the students of a
class, all the employees of an organization, and so on. Data type refers to the kind of data that may appear in the
computation of any program. Some of the frequently used data types are Real, Boolean, Character, Complex,
Numeric (Integer), Date, Alphanumeric, Graphics, String, Image, etc.

The syntax for declaring data type and the variable name is given below:
Syntax: < (data type)><variable names>;

The data types can be broadly classified as Built-in data type and abstract data type. Every programming
language contains a set of data types called built-in data types. For example, Data types in C: int, float, char, double,
enum, etc. Data types in FORTRAN: INTEGER, REAL, LOGICAL, COMPLEX, DOUBLE PRECISION,
CHARACTER, etc. Pascal: Integer, Real, Character, Boolean, etc.

The built-in data types are advantageous in processing various types of data. For instance, if a variable is
declared of the type Real, then several things are automatically implied, such as how to store a value for that
variable, what amount of memory is required to store, etc. When a program requires a special type of data that is not
available as a built-in data type, then it is implemented by the user on its own. This implemented special type of data
is termed as an abstract data type. It’s also known as a user-defined data type. In such a type of data, the user has
to give more effort regarding how to store value for that data, operations to manipulate variables of that kind of data,
etc. For example, to process a date (dd/mm/yy), no built-in data type is available in C, FORTRAN, and Pascal. This
can be accomplished using an abstract data type.

1.3 Data Structures:

The logical or mathematical model used to organize the data in main memory is called a data
structure. Various data structures are available each with its special features. These features should be kept in mind
while choosing a data structure for a particular situation. Generally, the choice of any data structure depends on its
simplicity and effectiveness in processing data. In addition, we also consider how well it represents the actual
relationship between the data in the real world. Data structures are helpful for programmers to manipulate and store
the data effectively. They help in establishing the relationship of one data element with other data elements. Various
methods are provided by data structures to organize and represent the data in the computer’s memory. The data
structures also govern the dynamic behavior towards data handling. Different ways of data organization
 require different kinds of data structures. Basically, two complementary goals are implemented by data
structures. The first goal is to develop mathematical entities and operations to solve particular problems. The
second goal is to search for suitable representations for these entities and then carry out the desired
operations. The second goal requires high-level data types to solve the problems. These high-level data types use
existing data types. Generally, the following additional goals are involved in producing quality data structure to have
quality software implementation:

 Correctness: The design of a data structure should be such that it can operate correctly for all kinds of input, based
on the domain of interest. For example, a data structure designed to store a collection of numbers, in a specific
order, must make sure that the numbers are not stored in an unorganized way.

 Efficiency: The data structure must be efficient to process the data at high speed without utilizing much of the
computer memory. On the basis of their implementation, the data structures are divided into two categories, namely
Primitive data structure and Non-primitive data structure. The primitive data structures further include Integer, Real,
Character, and Boolean. The non-primitive data structures are further divided into two groups: Linear and Non- linear
data structures. Arrays, linked lists, stacks, and queues are linear data structures while Trees and graphs are non-
linear data structures. All these are discussed in the
upcoming units in detail.

1.4 Abstract Data Types:

 The data type whose behavior is defined as a set of values and a set of operations is known to be Abstract data type
(ADT). ADT only mentions what operations are to be performed but not about the process of the operations to be
implemented. It is known as “abstract” as it provides an implementation-independent view. Hiding the main details
and providing only the essentials is known as abstraction.

 An Abstract Data Type [ADT] consists of two parts, namely, a value definition and an operator definition. A value
definition consists of a definition clause and a condition clause. The operator definition consists of three parts: a
header, preconditions, and post-conditions. The preconditions and post-conditions are optional and can be used
depending on the program requirement.

 As shown in figure 1.2, the ADT model has two different parts- Functions (public and private) and Data structures.
Both of these parts are confined to ADT and not a part of the application program. Data is entered, accessed,
modified, and deleted through the external application programming interface. This interface can access only public
functions. Every ADT operation has an algorithm to perform a specific task. Generally, three types of ADTs are
defined: List ADT, Stack ADT, and Queue ADT.

 List ADT: The data is generally stored in a sequence in the form of a list that has a head structure consisting of
count, pointers, and address of compare function needed to compare the data in the list. The data node contains the
pointer to a data structure and another pointer that points to the next node in the list. Some of the operations
performed on such list ADTs are:
 get() – Return an element from the list at any given position.
 insert() – Insert an element at any position of the list.
 remove() – Remove the first occurrence of any element from a non-empty list.
 removeAt() – Remove the element at a specified location from a non-empty list.
 replace() – Replace an element at any position by another element.
 size() – Return the number of elements in the list.
 isEmpty() – Return true if the list is empty, otherwise return false.
 isFull() – Return true if the list is full, otherwise return false.

 Stack ADT: In stack ADTs, the pointer to data is stored in the nodes in place of the data itself. Memory is allocated
for the data and the address is sent to the stack ADT. The head node and data nodes are encapsulated in ADT.
 Only a pointer to the stack is displayed to the calling function. The stack head contains a pointer to the top and also
a count of the number of entries present in the stack. Conceptually, a stack is an arrangement of the same type of
elements in sequential order. The operations take place only at the top end of the stack. Some of the operations
performed on stack ADTs are:
 push() – Insert an element at one end of the stack called top.
 pop() – Remove and return the element at the top of the stack, if it is not empty.
 peek() – Return the element at the top of the stack without removing it, if the stack is not
empty.
 size() – Return the number of elements in the stack.
 isEmpty() – Return true if the stack is empty, otherwise return false.
 isFull() – Return true if the stack is full, otherwise return false.

 Queue ADT: In a queue ADT, each node contains a void pointer to the data and the link pointer to the next element
in the queue. The same type of elements is arranged in sequential order and operations take place at both the ends
of a queue. Insertion is done at the end while deletion is done at the front. Some of the operations performed on
stack ADTs are:
 enqueue() – Insert an element at the end of the queue.
 dequeue() – Remove and return the first element of the queue, if the queue is not empty.
 peek() – Return the element of the queue without removing it, if the queue is not empty.
 size() – Return the number of elements in the queue.
 isEmpty() – Return true if the queue is empty, otherwise return false.
 isFull() – Return true if the queue is full, otherwise return false.

1.5 Summary:

 Data is a value or a collection of values that may be obtained from an experiment, survey, etc.
 A set of data items are used to represent a thing in the real world with the physical or the logical existence called an
entity.
 Data type refers to the kind of data that may appear in the computation of any program. Some of the frequently used
data types are Real, Boolean, Character, complex, numeric (integer), date, alphanumeric, graphics, string, Image,
etc. The data types can be broadly classified as Built-in
 data type and abstract data type.
 The logical or mathematical model used to organize the data in main memory is called a data structure. The data
structures are divided into two categories, namely primitive data structure and non- primitive data structure.
 The data type whose behavior is defined as a set of values and a set of operations is known to be Abstract data type
(ADT). ADT only mentions what operations are to be performed but not about the process of the operations to be
implemented.

1.6 Key Terms:

 Data item: A single unit of values.

 Entity: A set of data items used to represent a thing in the real world with the physical or the logical
existence.
 Data structure: The logical or mathematical model used to organize the data in main memory.
 Abstraction: Hiding the main details and providing only the essentials is known as abstraction.
 Application Program:
 Data item: A single unit of values.
 Entity: A set of data items used to represent a thing in the real world with the physical or the logical
existence.
 Data structure: The logical or mathematical model used to organize the data in main memory.
 Abstraction: Hiding the main details and providing only the essentials is known as abstraction.
 Application Program: A program designed to perform a particular function directly for the user or for
another application program.

1.7 Check Your Progress:

1. Short- Answer type

Q1) Abstract Data types provide an implementation-independent view. True/ False?
Q2) Define a data structure.
Q3) Which of the following is not a linear data structure?
(a) Stack (b) Queue (c) Tree (d) Linked List
Q4) _________ are also known as user-defined data types.
Q5) The two different parts of the ADT model are functions and __________.

2. Long- Answer type

Q1) Differentiate between Built-in and Abstract Data types
Q2) Explain the basic concept of data types.
Q3) Give the classification of Data structures.
 Q4) What are Abstract Datatypes? Explain its types.
Q5) Briefly explain the Abstract data type (ADT) model.

UNIT – 02 PRIMITIVE AND NON PRIMITIVE DATA STRUCTURE

Structure:
2.0 Introduction
2.1 Unit Objectives
2.2 Primitive Data Structures
2.3 Operations on Primitive Data Structures
2.4 Non- primitive Data Structures
2.4.1 Linear Data Structures
2.4.2 Non- Linear Data Structures
2.5 Operations on Non- primitive Data Structures
2.6 Summary
2.7 Key Terms
2.8 Check Your Progress

2.0 Introduction:
We are already familiar with the definition of a data structure. Data structure provides a set of
variables being associated with each other in different ways. Various programming languages utilize these variables
to represent relationships between data elements and help in the easy processing of data. According to their
utilization in distinct programming languages, data structures are classified as Primitive and non-primitive data
structures. This unit explains the use and representation of Primitive data structures in detail.

2.1 Unit Objectives:

After going through this unit, the reader will be able to:
 Understand the basic concept of primitive data structures.
 Explain the use and representation of different primitive data structures.

2.2 Primitive Data Structures:

The primitive data structures are used to represent numbers and characters that are included in the built-in
programs. They are the basic data types of any programming language and are not composed of other data types.
They can be manipulated or can even be operated directly with the help of machine-level instructions. Primitive data
structures include basic data types like Integer, Real, Character, and Boolean.

1. Integer: The integral or fixed-precision values are represented by integers (denoted as int). The type INTEGER
includes a subset of the whole numbers with a variation in size for different computer systems. All the operations on
this type of data are precise and also follow the basic laws of arithmetic. Though arithmetic operations yield accurate
results if the result of such operations lies outside the subset, then the computation might fail.

2. Real: The REAL primitive data type includes a subset of the real numbers. The arithmetic operations performed on
the REAL data types can be incorrect within the limits of round-off errors while the arithmetic performed on
INTEGER type yield accurate results. This is considered to be the main difference between the REAL and INTEGER
data type.

3. Character: Denoted as Char, the character primitive data type consists of a set of structured and printable
characters with 26 upper case letters, 26 lower case letters, 10 decimal digits, and various other graphic characters
like punctuation marks. Every computer system stores character data in a one-byte field as an integer value. One
byte comprises 8 bits so it has 256 possibilities having positive values of 0 to 255.

4. Boolean: This primitive data structure is used for Boolean values that are denoted by two identities TRUE and
FALSE. The Boolean operators include logical conjunction (&), disjunction (OR), and negation (~).

2.3 Operations on Primitive Data Structures:

Several operations can be performed on primitive data structures. Some of the general operations are:

1. Creation Operation: The creation operation creates a data structure. For example: int x; Here, the above-declared
statement will create 2 bytes of memory space for variable ‘x’. This variable will be used to store only integer values.

2. Destroy Operation: The destroy operation destroys the data structure. In C language, ‘free()’ operation is used to
destroy the data structure. This helps using the memory of the system efficiently.

3. Selection Operation: The selection operation is used to access data within a data structure. The significance of the
selection operation is provided in a file data structure.

4. Update Operation: To modify data in the data structure, the update operation is used.
2.4 Non- primitive Data Structures:
The data structures derived from primitive data structures are known as Non-primitive data structures. These
data structures cannot be manipulated or operated directly by machine-level instructions. A set of either
homogeneous (same data type) or heterogeneous (different data type) data elements are formed. These are further
divided into linear and non-linear data structures based on the structure and arrangement of data.

2.4.1 Linear Data Structures:

The linear data structure is the one in which its elements form a sequence. It means each element in the
structure has a unique predecessor and a unique successor. An array is the simplest linear data structure. Various
other linear data structures are linked lists, stacks, and queues.

 Arrays: A finite collection of homogeneous elements is termed as an array. Here, the word ‘homogenous’ indicates
that the data type of all the elements in the collection should be the same, that is, int or char or float or any other
built-in or user-defined data type. However, an array cannot have elements of two or more data types together.
Elements of an array are always stored in contiguous memory locations irrespective of the array size. The elements
of an array can be referred to by using one or more indices or subscripts. An index or subscript is a positive integer
value that indicates the position of a particular element in the array. If the number of subscripts required to access
any particular element of an array is one, then it is a single-dimensional array. Otherwise, it is a multidimensional
array. The multi-dimensional array may be a two-dimensional array or even more. Consider a single-dimensional
array Arr with size n, where n is the maximum number of elements that Arr can store. Mathematically, the elements
of Arr are denoted as Arr1, Arr2, Arr3,..., Arr n. In different programming languages, array elements are denoted by
different notations, such as by parenthesis notation or by bracket notation. Table 1.1 shows the notation of elements
of a single-dimensional array Arr with size n in different programming languages.

S.No. Notation Programming Language(s)

01 Arr(1), Arr(2), Arr(3),..... Arr(n) BASIC and FORTRAN
02 Arr[1], Arr[2], Arr[3],...... Arr[n] PASCAL
03 Arr[0], Arr[1], Arr[2],...... Arr[n-1] C, C++ and JAVA
Table 1.1 Different Notations of a Single-dimensional Array

Note that in the languages like BASIC, PASCAL, and FORTRAN, the smallest subscript value is 1 and the
largest subscript value is n. On the other hand, in languages like C, C++, and Java, the smallest subscript value is 0
and the largest subscript value is n–1. In general, the smallest subscript value used to access an array element is
the lower bound b) and the largest subscript value is the upper bound (Ub).

In two-dimensional arrays, the elements can be viewed as arranged in the form of rows and columns (matrix
form). To access an element of a two-dimensional array, two subscripts are used—the first one represents the row
number and the second one represents the column number. Consider a two-dimensional array Arr with size m*n,
where m and n represent the number of rows and columns respectively. Mathematically, the array Arr is denoted as
Arrij, where i and j indicate row number and column number with i< = m and j<= n. Table 1.2 shows the notation of
elements of a two-dimensional array Arr in different programming languages.

S.No. Notation Programming Language(s)

01 Arr(i, j) with 0<i<=m and 0<j<=n BASIC and FORTRAN
02 Arr[i, j] with 0<i<=m and 0<j<=n PASCAL
03 Arr [i] [j] with 0<=i<m and 0<=j<n C, C++ and JAVA
Table 1.2 Different Notations of a Two-dimensional Array

 Linked Lists: A linked list is a linear collection of similar data elements, called nodes, with each node containing
some data and pointer(s) pointing to other nodes (s) in the list. Nodes of a linked list are not constrained to be at
contiguous memory locations; instead, they can be stored anywhere in the memory. The linear order of the list is
maintained by the pointer field(s) in each node.

 Unit 3 – Linked Lists
Structure:
3.0 Introduction
3.1 Unit Objectives
3.2 Singly-Linked Lists
3.2.1 Memory Representation
3.2.2 Operations
3.3 Circular Linked Lists
3.3.1 Traversing
3.3.2 Insertion
3.3.3 Deletion
3.4 Doubly-Linked Lists
3.4.1 Insertion
3.4.2 Deletion
3.5 Dynamic Storage Management: Application of a Doubly-Linked List
3.6 Generalized Lists
3.7 Garbage Collection
3.8 Summary
3.9 Key Terms
3.10 Check Your Progress

3.0 Introduction:
In the simplest terms, a list refers to a collection of data items of similar type arranged in a sequence
(that is, one after another), e.g., list of students’ names, list of addresses, etc. One way to store such lists in memory
is to use an array. However, arrays have certain problems associated with them. As array elements are stored in
adjacent memory locations, a sufficient block of memory is allocated to an array at compilation time. Once the
memory is allocated to an array, it cannot be expanded or contracted. This is why an array is called a static data
structure. If the number of elements to be stored in an array increases or decreases significantly at run-time, it may
require more memory space or may result in wastage of memory, both of which are unacceptable. Another problem
is that the insertion and deletion of an element into an array are expensive operations, since they may require a
number of elements to be shifted. As a result of these problems, arrays are not generally used to implement linear
lists; instead, another data structure known as a linked list is used. A linked list is a linear collection of homogeneous
elements called nodes. The successive nodes of a linked list need not occupy adjacent memory locations and the
linear order between the nodes is maintained by means of pointers. This unit discusses different types of linked lists,
such as singly-linked lists, circular linked lists, and doubly-linked lists, and the various operations, such as creation,
traversal, search, insertion, and deletion, that can be performed on them. It also discusses how data structures,
stacks, and queues are implemented using linked lists.

3.1 Unit Objectives: After going through this unit, the reader will be able to:

 Explain the singly linked list data structure.

 Understand the salient features and applications of circular linked lists.
 Understand the salient features and applications of doubly-linked lists, including dynamic storage management.
 Describe the applications of generalized lists.
 Explain the meaning and applications of garbage collection.

3.2 Singly-Linked Lists:

In a singly-linked list (also called linear linked list), each node consists of two fields: info and next (Figure 3.1). The
info field contains the data and the next field contains the address of the memory location where the next node is
stored. The last node of the singly-linked list contains NULL in its next field that indicates the end of the list. Figure
3.1 Node of a linked list.

The data stored in the info field may be a single data item of any data type or a complete record representing a
student or an employee or any other entity. In this unit, however, we assume the info field contains integer data. As
each node of the list contains only a single pointer pointing to the next node (not to the previous node) thereby
allowing traversing in only one direction, it is also referred to as a one-way list. Figure 3.2 shows a singly-linked list
with four nodes. Figure 3.2 A Singly-linked List with Four Nodes.

The linked list overcomes all the drawbacks of arrays. It is a dynamic data structure, which implies that the memory
is allocated dynamically at run-time. Also, there is no upper limit on the size of the linked list and new nodes can be
 inserted into it as far as memory is available. Moreover, since the successive nodes of a linked list are stored in non-
contiguous memory locations, nodes can be inserted or deleted without shifting of the existing nodes.

3.2.1 Memory Representation:

To maintain a linked list in memory, two parallel arrays of equal size are used. One array (say, INFO) is used
for the info field, and another array (say, NEXT) for the next field of the nodes of the list. The values in the arrays are
stored such that the ith location in arrays INFO and NEXT contain, respectively, the info and next fields of a node of
the list. In addition, a pointer variable Start is maintained in memory that stores the starting address of the list. Figure
3.3 shows the memory representation of a linked list where each node contains an integer.

Figure 3.22 Deletion from the beginning of a doubly-linked list.

In this figure, the pointer variable Start contains 25, that is, the address of the first node of the list, which stores the
value 37 in array INFO and its corresponding element in array NEXT stores 49, that is, the address of the next node
in the list, and so on. Finally, the node at address 24 stores value 69 in array INFO and NULL in array NEXT, thus, it
is the last node of the list. Note that the values in array INFO are stored randomly and the array NEXT is used to
keep track of the values in the list.

Memory Allocation:
As memory is allocated dynamically to the linked list, a new node can be inserted anytime in
the list. For this, the memory manager maintains a special linked list known as a free-storage list or memory bank or
free pool that consists of unused memory cells. This list keeps track of the free space available in the memory and a
pointer to this list is stored in a pointer variable Avail (Figure 3.4). Note that the end of the free-storage list is also
denoted by storing NULL in the last available block of memory.

Figure 3.4 Free- storage List In this figure, Avail contains 22, hence, INFO[22] is the starting point of the free-storage
list. Since NEXT[22] contains 26, INFO[26] is the next free memory location. Similarly, other free spaces can be
accessed and the NULL in NEXT[23] indicates the end of the free-storage list. While creating a linked list or inserting
an element into a linked list, whenever a request for the new node arrives, the memory

Algorithm 3.22 Deletion from the beginning delete_beg(Start)

1. If Start = NULL
Print “Underflow: List is empty!” and go to step 6
End If
2. Set temp = Start //temp points to the node to be deleted
3. Set Start = Start->next //making Start to point to next node
4. Set Start->prev = NULL
5. Deallocate temp //de-allocating memory
6. End
Note:
The process of deleting a node from the end of a doubly-linked list is the same as that of the
singly-linked list.
To delete a node from a position (say, pos) specified by the user, the list is traversed up to the pos
position using pointer variables temp and save. At the end of traversing, temp points to the node at the
pos position and save points to the node at the pos-1 position. Here, for simplicity, we use another
pointer variable ptr to point to the node at the pos+1 position. Then, the next field of the node at pos-1
position (pointed to by save) is made to point to the node at pos+1 position (pointed to by ptr). In
addition, the prev field of the node at pos+1 position (pointed to by ptr) is made to point to the node at
pos-1 position (pointed to by save). After that, the memory occupied by the node pointed to by temp is
de-allocated. Figure 3.23 shows the deletion of a node at the third position from a doubly-linked list.
Figure 3.23 Deletion from a Specified Position of a doubly-linked list
Algorithm 3.23 Deletion from a Specified Position
delete_pos(Start)
1. If Start = NULL
Print “Underflow: List is empty!” and go to step 8
End If
2. Set temp = Start
3. Read pos
4. Call count_node(temp) //counting total number of nodes in count variable
5. If pos > count OR pos = 0
Print “Invalid position!” and go to step 6
End If
6. If pos = 1
Set Start = Start->next //deleting the first node
Start->prev = NULL
Else
Set i = 1
While i < pos //traversing up to the node at pos position
Set save = temp //save pointing to the node at pos-1 position
Set temp = temp->next //making temp to point to next node
Set i = i + 1
End While
Set ptr = temp->next
Set save->next = ptr
Set ptr->prev = save
End If
7. Deallocate temp //deallocating memory
8. End
Note:
A doubly-linked list in which the next field of the last node points to the first node instead of
NULL is termed as a doubly-circular linked list.
Program 4.4:
A program to illustrate the implementation of a doubly-linked list.
#include<stdio.h>
#include<conio.h>
#define True 1
#define False 0
typedef struct node
{
int info;
struct node *next;
struct node *prev;
}Node;
/* node of a doubly linked list */
/* Function prototypes */
Node * create_node();
int isempty(Node *);
void display(Node *);
int count_node(Node *);
void insert_beg(Node **);
void insert_end(Node **);
void insert_pos(Node **);
void delete_beg(Node **);
void delete_end(Node **);
void delete_pos(Node **);
/*Main Function*/
doubly-linked list.
Figure 3.20 Insertion at the end of a doubly linked list
Algorithm 3.20 Insertion at the end
insert_end(Start)
1. Call create_node() //creating a new node pointed to by nptr
2. If Start = NULL
Set Start = nptr //inserting new node as the first node
 Else
Set temp = Start //pointer temp used for traversing
While temp->next != NULL
Set temp = temp->next
End While
Set temp->next = nptr
Set nptr->prev = temp
End If
3. End
To insert a new node (pointed to by nptr ) at a specified position (say, pos ) in a doubly-linked list, the
list is traversed up to the pos-1 position. At the end of traversing, temp points to the node at the pos-1
position. For simplicity, we use another pointer variable (say, ptr ) to point to the node that is already at
the pos position. Then, the prev field of the node pointed to by ptr is made to point to the new node and
the next field of the new node is made to point to the node pointed to by ptr. Also, the prev field of the
new node is made to point to the node pointed to by temp and the next field of the node pointed to by
temp is made to point to the new node. Figure 3.21 shows the insertion of a new node at the third
position in a doubly-linked list.
Figure 3.21 Insertion at a specified position of a doubly linked list
Algorithm 3.21 Insertion at a Specified Position
insert_pos (Start)
1. Call create_node() //creating a new node pointed to by nptr
2. Set temp = Start
3. Read pos
4. Call count_node(temp) //counting number of nodes in count variable
5. If pos = 0 OR pos > count + 1
Print “Invalid position!” and go to step 7
End If
6. If pos = 1
Set nptr->next = Start //inserting node at the beginning
Set Start = nptr //Start pointing to new node
Else
Set i = 1
While i < pos-1 //traversing up to the node at pos-1 position
Set temp = temp->next
Set i = i + 1
End While
Set ptr = temp->next
Set ptr->prev = nptr
Set nptr->next = ptr
Set nptr->prev = temp
Set temp->next = nptr
End If
7. End

3.4.2 Deletion:
To delete a node from the beginning of a doubly-linked list, a pointer variable (say, temp ) is used to point to
the first node. Then Start is modified to point to the next node and the prev field of this node is made to point to
NULL. After that, the memory occupied by the node pointed to by temp is de-allocated. Figure 3.22 shows the
deletion of a node from the beginning of a doubly-linked list.
3. Display
4. Exit
Enter your choice: 4
3.4 Doubly- Linked Lists
In a singly-linked list, each node contains a pointer to the next node and it has no information about its
previous node. Thus, we can traverse only in one direction, that is, from beginning to end. However,
sometimes it is required to traverse in the backward direction, that is, from end to the beginning. This
can be implemented by maintaining an additional pointer in each node of the list that points to the
previous node. Such a type of linked list is called the doubly-linked list.
Each node of a doubly-linked list consists of three fields: prev, info, and next (Figure 3.17). The info
field contains the data, the prev field contains the address of the previous node and the next field
contains the address of the next node.
Figure 3.17 Node of a Doubly-linked List
Since a doubly-linked list allows traversing in both forward and backward directions, it is also referred
to as a two-way list. Figure 3.18 shows an example of a doubly-linked list having four nodes. Note that
the prev field of the first node and the next field of the last node in a doubly-linked list points to NULL.
Figure 3.18 An Example of a Doubly-linked List with Four Nodes
To define the node of a doubly-linked list in the ‘C’ language, the structure used to represent the node of
the singly-linked list is extended to have an extra pointer, which points to the previous node. The
structure of a node of a doubly-linked list is shown here.
typedef struct node
{
int info;
/*to store integer type data*/
struct node *next;
/*to store a pointer to next node*/
struct node *prev;
/*to store a pointer to previous node*/
}Node;
Node *nptr;
/*nptr is a pointer to node*/
When memory is allocated successfully to a node, that is, there is no overflow, the node is initialized.
The info field is initialized with a valid value and the prev and next fields are initialized with NULL.
Algorithm 3.18 Creating a Node of Doubly Linked List
create_node()
1. Allocate memory for nptr //nptr is a pointer to a new node
2. If nptr = NULL
Print “Overflow: Memory not allocated!” and go to step 8
3. Read item //item is the value stored in the node
4. Set nptr->info = item
5. Set nptr->next = NULL
6. Set nptr->prev = NULL
7. Return nptr
8. End
Note that all the operations that are performed on singly-linked lists can also be performed on doubly-
linked lists. In this section, we will discuss only insertion and deletion operations on doubly-linked lists.
3.4.1 Insertion
To insert a new node at the beginning of a doubly-linked list, a pointer (say, nptr ) to a new node is
created. The next field of the new node is made to point to the existing first node and the prev field of
the existing first node (that has become the second node now) is made to point to the new node. After
that, Start is modified to point to a new node. Figure 3.19 shows the insertion of a node at the beginning
of a doubly-linked list.
Figure 3.19 Insertion at the beginning of a doubly-linked list
Algorithm 3.19 Insertion in the Beginning
insert_beg(Start)
1. Call create_node() //creating a new node pointed to by nptr
2. If Start != NULL
Set nptr->next = Start //inserting node in the beginning
Set Start->prev = nptr
End If
3. Set Start = nptr //making Start point to the new node
4. End
To insert a new node at the end of a doubly-linked list, the list is traversed up to the last node using some pointer
variable (say, temp ). At the end of traversing, temp points to the last node. Then, the next field of the last node (pointed to
by temp) is made to point to the new node and the prev field of the new node is made to point to the node pointed to by
temp. However, if the list is empty, the new node is inserted as the first node in the list. Figure 3.20 shows the insertion of a
new node at the end of a return;
}
if(temp->next==*Start)
*Start=NULL;
else
{
while(temp->next != *Start)
{
save=temp;
temp=temp->next;
}
save->next=*Start;
}
free(temp);
printf(“\nNode deleted.”);
}
The output of the program is:
Main Menu
1. Insert 2. Delete 3. Display 4. Exit
Enter your choice: 1
1. Insert in the beginning 2. Insert at the end 3. Back to main menu
Enter your choice: 1
Enter the value to be inserted: 5
Node inserted.
Main Menu
1. Insert 2. Delete 3. Display 4. Exit
Enter your choice: 1
1. Insert in the beginning 2. Insert at the end 3. Back to main menu
Enter your choice: 1
Enter the value to be inserted: 4
Node inserted.
Main Menu
1. Insert 2. Delete 3. Display 4. Exit
Enter your choice: 1
1. Insert in the beginning 2. Insert at the end 3. Back to main menu
Enter your choice: 2
Enter the value to be inserted: 6
Node inserted.
Main Menu
1. Insert 2. Delete 3. Display 4. Exit
Enter your choice: 3
The linked list is: 4 5 6
Main Menu
1. Insert 2. Delete 3. Display 4. Exit
Enter your choice: 2
1. Delete from the beginning 2. Delete from the end 3. Back to main menu
Enter your choice: 1
Node deleted.
Main Menu
1. Insert 2. Delete 3. Display 4. Exit
Enter your choice: 3
The linked list is: 5 6
Main Menu
1. Insert 2. Delete 3. Display 4. Exit
Enter your choice: 2
1. Delete from the beginning 2. Delete from the end 3. Back to main menu
Enter your choice: 2
Node deleted.
Main Menu
1. Insert 2. Delete 3. Display 4. Exit
Enter your choice: 3
The linked list is: 5
Main Menu
1. Insert 2. Delete