UNIT III LINEAR DATA STRUCTURES

Abstract Data Types (ADTs) – List ADT – Array-Based Implementation – Linked List –
Doubly- Linked Lists – Circular Linked List – Stack ADT – Implementation of Stack –
Applications – Queue ADT – Priority Queues – Queue Implementation – Applications.
UNIT-III / PART-A
1 Define Abstract Data Type (ADT). What are operations of ADT? (May 15,16, Dec 15,19)
An abstract data type (ADT) is the way we look at a data structure, focusing on what it
does and ignoring how it does its job. An ADT is a set of elements with a collection of
well-defined operations. Union, Intersection, size, complement and find are the various
operations of ADT.
Examples of ADTs include list, stack, queue, set, tree, graph, etc
2 What is Data Structure?
A data structure is basically a group of data elements that are put together under one
name, and which defines a systematic way of storing and organizing data either in
computer’s memory or on the disk storage so that it can be used efficiently.
Some common examples of data structures are arrays, linked lists, queues, stacks,
binary trees and hash tables
3 Why Data Structures?
Data structures study how data are stored in a computer so that operations can be
implemented efficiently. Data structures are especially important when you have a
large amount of information. Conceptual and concrete ways to organize data for
efficient
storage and manipulation.
4 Draw the classification diagram of data structures.

5 List out the operations on linear Data Structures.

 Traversal: Visit every part of the data structure.
 Search: Traversal through the data structure for a given element.
 Insertion: Adding new elements to the data structure.
 Deletion: Removing an element from the data structure.
 Sorting : Rearranging the elements in some type of order(e.g Increasing or
Decreasing)
 Merging: Combining two similar data structures into one.
 CS3353- C Programming and Data Structures
6 Distinguish between linear data structures from non-linear data structures.
Linear data structure Non-linear data structure
 Data is arranged in linear sequence.  Data is not arranged in sequence.
 They are easy to implement in  They are difficult to implement in
computer’s memory since they are computer’s memory since the data
organized sequentially. element can be attached to various
other data elements.
 Example: List, Stacks, Queue etc.  Example: Tree, Graph etc.
7 List out the applications of data structures.
 Compiler design
 Operating system
 Statistical analysis package
 DBMS
 Numerical analysis
 Simulation
 Artificial intelligence
 Graphics
8 Give the classification of data structures.
Data structures are generally categorized into two classes: primitive and non-
primitive data Structures.
 Primitive data structures are the fundamental data types which are supported
by a programming language. Some basic data types are integer, real, character,
and boolean. The terms ‘data type’, ‘basic data type’, and ‘primitive data type’ are
often used interchangeably.
 Non-primitive data structures are those data structures which are created
using primitive data structures. Examples of such data structures include
linked lists, stacks, trees, and graphs. Non-primitive data structures can
further be classified
into two categories: linear and non-linear data structures.
9 Define Lists.
A list, also called a sequence, is a container that stores elements in a certain linear order,
which is imposed by the operations performed. The basic operations supported are
retrieving, inserting, and removing an element given its position. Special types of lists
include stacks and queues, where insertions and deletions can be done only at the head
or the tail of the sequence. The basic realization of sequences is by means of arrays and
linked lists.
10 Define List Abstract Data Type.
A list is a sequence of zero or more elements of a given type a1, a2, . . . , an (n ≥ 0)
 n : length of the list
 a1 : first element of the list
 an : last element of the list
 n = 0 : empty list
 elements can be linearly ordered according to their position in the list
We say ai precedes ai+1, ai+1 follows ai, and ai is at position i.
 CS3353- C Programming and Data Structures
11 What are the various operations done under list ADT?
 Print list
 Insert
 Make empty
 Remove
 Next
 Previous
 Find kth
12 What are the different ways to implement list?
There are two ways to implement list
 Simple array implementation of list
 Linked list implementation of list
13 Write the Array Implementation of Lists.
 Here, elements of list are stored in the (contiguous) cells of an array.
 List is a structure with two members.
member 1 : an array of elements
member 2 : last — indicates position of the last element of the list
14 What are the disadvantages of array-based implementation?
 Arrays are of fixed size.
 Data elements are stored in contiguous memory locations which may not be
always available.
 Insertion and deletion of elements can be problematic because of shifting of
elements from their positions.
15 Why linked list is called as self-referential data type?
In a linked list, every node contains a pointer to another node which is of the same
type; it is also called a self-referential data type.
16 What is meant by a Linked List? or Define linked list. (Dec 19)
Linear list is defined as item in the list called a node and contains two fields, an
information field and next address field. The information field holds the actual
element on the list. The next address field contains the address of the next node
in the list.

17 How is an element of a linked list called? What will it contain?

Linked list or list is an ordered collection of elements. Each element in the list is
referred as a node. Each node contains two fields namely,
 Data field
 Link field
18 What is free pool?
The computer maintains a list of all free memory cells. This list of available space is
called the free pool.
 CS3353- C Programming and Data Structures
19 Give the comparison between array and linked list. (Dec 18,20)
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.
20 List out the advantages of linked lists. (May 14,15)
What are the advantages of linked lists over arrays? (May 19)
Linked lists have many advantages. Some of the very important advantages are:
 Linked lists are dynamic data structures. i.e., they can grow or shrink during the
execution of a program.
 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.
 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.
 Many complex applications can be easily carried out with linked lists.
21 What are the disadvantages of linked list over array? (Dec 18)
 The main disadvantage of linked list over array is access time to individual
elements. Array is random-access, which means it takes O(1) to access any element
in the array. Linked list takes O(n) for access to an element in the list in the
worst case.
 Another advantage of arrays in access time is special locality in memory. Arrays
are defined as contiguous blocks of memory, and so any element will be
physically near its neighbors. This greatly benefits from modern CPU caching
methods.
 In linked list, Random access is not allowed. We have to access elements
sequentially starting from the first node. So we cannot do binary search with
linked lists.
 Extra memory space for a pointer is required with each element of the list. Hence
Linked lists wastes memory in terms of extra reference points.
 CS3353- C Programming and Data Structures
22 What are the types of Linked Lists?
Singly Linked List, Circular Linked List, Doubly Linked List and Circular Doubly Linked
List.
23 What is singly 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 singly linked list allows traversal of
data only in one way.

24 What is the use of header in a linked list?

A linked list contains a pointer, referred as the head pointer, which points to the first
node in the list that stores the address of the first node of the list.
25 What are the operations can we perform on a linked list? (May 14)
The basic operations that can be performed on linked list are,
 Creation of a list.
 Insertion of a node.
 Modification of a node.
 Deletion of a node.
 Traversal of a node.
26 Give the Structure definition of Singly
Linked List.
Struct slinklist
{
int data;
struct slinklist* next;
};typedef struct slinklist node;
node *start = NULL;
27 List out the applications of linked list.(Dec 20)
1. Linked lists are used to represent and manipulate polynomial. Polynomials are
expression containing terms with non-zero coefficient and exponents.
For example: P(x) = a0 Xn + a1 Xn-1 + …… + an-1 X + an
2. Represent very large numbers and operations of the large number such as addition
multiplication and division.
3. Linked lists are to implement stack, queue, trees and graphs.
4. Implement the symbol table in compiler construction
28 What is circular linked list? (Dec 14, May 16)
The circular linked list (CLL) is similar to singly linked list except that the last node’s
next pointer points to first node. The list will be accessed like a chain. Circular linked list
can be used to help the traverse the same list again and again if needed.
 CS3353- C Programming and Data Structures
29 Mention where circular linked lists are widely used?
 A circular linked list is used to maintain the sequence of the Web pages visited.
Traversing this circular linked list either in forward or backward direction helps to
revisit the pages again using Back and Forward buttons.
 Circular linked lists are widely used in operating systems for task maintenance.
 Multiplayer games uses circular list to swap between players in a loop.
30 Write the C structure definition of Doubly Linked Lists.
Struct node
{
struct node *prev;
int data; struct node *next; };
31 What is Doubly Linked Lists?

32 List out the applications of doubly linked list.

 Doubly linked list can be used in navigation systems where both front and
back navigation is required.
 It is used by browsers to implement backward and forward navigation of visited
web pages i.e. back and forward button.
 It is also used by various applications to implement Undo and Redo functionality.
 It can also be used to represent deck of cards in games.
 It is also used to represent various states of a game.
33 What is Circular doubly linked list?
A circular doubly linked list is one, which has both the successor pointer and
predecessor pointer in the 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.
 CS3353- C Programming and Data Structures
34 What are the advantages of circular linked list over linear linked list?
The major advantage of circular lists (over non-circular lists) is that they eliminate some
extra-case code for some operations (like deleting last node). Also, some applications lead
naturally to circular list representations. For example, a computer network might best be
modeled using a circular list.
35 List three operations possible for general list that are not allowed for either stacks or
queues?
Linked list are more flexible in regard to insertion and deletion and rearrangement
 Inserting a new entry at any position
 Delete a data at any position
 Retrieve data at any position
36 List out the applications of Circular doubly linked list.
 Managing songs playlist in media player applications.
 Managing shopping cart in online shopping.
37 Distinguish singly linked list with doubly linked list.
Singly linked list Doubly linked list
A singly linked list is a linked list where A doubly linked list is complex type of
the node contains some data and a pointer linked list where the node contains some
to the next node in the list data and a pointer to the next as well as the
previous node in the list
It allows traversal only in one way It allows a two way traversal
It uses less memory per node (single It uses more memory per node(two
pointer) pointers)
Complexity of insertion and deletion at a Complexity of insertion and deletion at a
known position is O(n) known position is O(1)
If we need to save memory and searching If we need better performance while
is not required, we use singly linked list searching and memory is not a limitation,
we go for doubly linked list
If we know that an element is located If we know that an element is located
towards the end section, eg. ‘zebra’ still we towards the end section e.g. ’zebra’ we can
need to begin from start and traverse the start searching from the Back.
whole list
Singly linked list can mostly be used for They can be used to implement stacks,
stacks heaps, binary trees.
38 What is static linked list? State any two applications of it. (May 15)
In Static Linked List, each node is allocated memory when it is to be inserted
dynamically. Each node contains a pointer pointing to the next node. But in Array List,
we store values in an array and have another array storing the indices of the nodes
which correspond to the next item in the list. There is one key array and one link array.
Since the memory allocated to an array is constant, it is static. The application of static
linked
list is to implement stack, hash table and binary tree.
 CS3353- C Programming and Data Structures
39 State the advantages of ADT. (Dec 18)
 Code is easier to understand (e.g., it is easier to see “high-level” steps being
performed, not obscured by low-level code).
 Implementations of ADTs can be changed (e.g., for efficiency) without
requiring changes to the program that uses the ADTs.
 ADTs can be reused in future programs.
40 Illustrate the difference between Linear Linked List and Circular Linked List. (May 19)
Two pointers are maintained in a node of Only one pointer is maintained in a node
circular list, one will keep the address of of singly list which contains the address of
first previous node and first next node in next node in sequence another will keep
sequence. the address of.
In circular list, we can move backward as In singly, we cannot move in backward
well as forward direction as each node direction because each in node has next
keeps the address of previous and next node pointer which facilitates us to move
node in sequence. in forward direction.
During deletion, we have to keep only During deletion of a node in between the
one node address i.e the node to be singly list, we will have to keep two nodes
deleted. address one the address of the node to be
This node will give the address of previous deleted and the node just previous of it.
node automatically.
UNIT-III / PART-B
1 Explain in detail about the linked list implementation using an example. State the
problems in freeing list node.
2 Write a program to reverse a linked list using recursion.
3 Write a routine to merge given two sorted linked lists. (Dec 15)
4 Write an algorithm to insert an element into a linked list. Explain it with an example (or)
Explain the insertion operation linked list. How nodes are inserted after a specified node?
(Dec 19)
5 Write and explain the algorithm to copy a linked list.
6 What are the operations on singly linked list? Explain with an example.
7 Write a C code for singly linked list with insert, delete, and display operations using
structure pointers. (May 16, Dec 18)
8 Describe the creation of a doubly linked list and appending the list. Give relevant coding C.
(Dec 14, May 14)
9 Illustrate the algorithm to implement the doubly linked list and perform all the
operations on the created list. (May 16)
10 Write a C program to concatenate two double linked lists.
11 Write an algorithm to insert a node at front and end of a circular linked list.
12 i) Make a comparison between a linked list and a linear array. Which one will you
prefer to use and when?
ii) Give the advantages and uses of circular linked lists.
13 Explain the applications of list.
14 Write a C program to perform addition, subtraction and multiplication operations on
polynomial using linked list. (May 15)
CS3353- C Programming and Data Structures
15 State the polynomial representation for 6x3+9x2+7x+1 using linked list. Write
 procedure
to add and multiply two polynomial and explain with suitable example. (Dec 18)
16 What are the various operations on array? Write a procedure to insert an element in the
middle of the array. (Dec 18)
17 Write a procedure to deleting the last node from a circular linked list. (Dec 18)
18 What are the applications of linked list in dynamic storage management? (Dec 19)
19 i) Write a program to merge two sorted linked list (P & Q – assume that they
are available) to get a single sorted list S.
Eg. P:1  2  45  56
Q: 3  24  56  63  66
ii) Write a non-recursive procedure to reverse a singly linked list. (May 19)
20 i) Write a function to add two polynomials represented by linked
representation. Apply the function for the following input.
A=3x14 + 2x18 + 1, B = 8x12 + 3x10 + 3x8 + 10x6
ii) Write a function to delete the node n from the given doubly linked
list. p  q  r  n  s  t  z . (May 19)
21 Define data abstraction. Write the ADT for the data structure in which the same
condition can used appropriately, for checking overflow and underflow. Define all
basic
functions of this ADT. (May 19)

to compute L1 ∩ L2 and L1 𝖴 L2.

22 i) Given two sorted Linked lists L1 and L2. Exemplify and write the functions

ii) State the advantages of Linked list over arrays. Specify any two real time
applications
of Linked list. (Dec 20)
23 i) Write an algorithm to perform following operations in a doubly linked list.
1) Insert a node at the end of the list
2) Delete the last node in the list.
ii) Analyze and write algorithm for Circular Linked list for the following operations
using structure pointer. 1) Insert 2) Delete 3) Display (Dec 20)