Learning Objectives:

• Describe the structure of a linked list node, including data and a pointer/reference to the next node in the list.
• Develop the ability to traverse a singly linked list to access and manipulate its elements, understanding the concept of the "current" node.
• Perform insertion and deletion operations at various positions within a singly linked list, including at the beginning, end, and middle.

A linked list is a linear collection of data elements. It has two parts: One is info and other is link part. Info part gives information and link part is address of next node.

Advantages of Linked list:

1. Linked lists are dynamic. Their size can be altered during runtime.
2. Memory-efficient.
3. Insertion and Deletion is easier.

Advantages of Linked list:

1. Consumes more space as additional space is required to store pointer address.

Basic Operations

1. Creation
2. Insertion
3. Deletion
4. Traversing: It is the process of accessing each node of the linked list exactly once to perform some operation.

Bluepokeboy, CC BY-SA 4.0, via Wikimedia Commons

Solved Example: 9968-01

Which type of linked list stores the address of the header node in the next field of the last node?

A. Singly linked list

B. Circular linked list

C. Doubly linked list

D. Hashed list

Correct Answer: B

Solved Example: 9968-02

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

A. $\theta (n)$

B. $\theta (n \log n)$

C. $\theta (n^2)$

D. $\theta (1)$

Correct Answer: C

Solved Example: 9968-03

In a doubly linked list, the number of pointers affected for an insertion operation will be:

A. 4

B. 0

C. 1

D. Depends upon the nodes of the doubly linked list

Correct Answer: D

Learning Objectives:

• Define key terminology related to trees, such as nodes, edges, root, parent, child, leaf, height, depth, and level.
• Identify and understand different types of trees, including binary trees, binary search trees, balanced trees (e.g., AVL and Red-Black trees), and multi-way trees.
• Understand the representation of binary trees using arrays and linked structures, and compare their advantages and disadvantages.

A tree is a non-empty set, one element of which is designed the root of the tree while the remaining elelments are partitioned into non-empty sets each of which is a sub-tree of the root.

1. Leaf Node:
2. Path:
3. Siblings
4. Ancestors and Descendent
5. Subtree
6. Level

Solved Example: 9971-01

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is:

A. $\Omega(\log n)$

B. $(n)$

C. $(n \log n)$

D. $(n^2)$

Correct Answer: A

Solved Example: 9971-02

Which data structure is used for storing a collection of elements in a non-linear fashion?

A. Array

B. Stack

C. Queue

D. Tree

A tree is a non-linear data structure used for storing a collection of elements. It is composed of nodes, where each node contains a value and a pointer to its child nodes.

Correct Answer: D

Learning Objectives:

• Understand the concept of vectors (dynamic arrays) as a data structure for storing and manipulating collections of elements.

A one-dimensional array is like a list; A two dimensional array is like a table.

Some texts refer to one-dimensional arrays as vectors, two-dimensional arrays as matrices.

Solved Example: 9511-01

Which of the following is not a data structure?

A. Stack

B. Queue

C. Function

D. Linked list

Correct Answer: C

Learning Objectives:

• Understand the role of data structures in storing and organizing data efficiently.
• Differentiate between basic data structures like arrays, linked lists, stacks, and queues.

• A structure is a collection of variables of different data types under a single name.
• The variables are called members of the structure.
• The structure is also called a user-defined data type.

• Structure is a user-defined data type (such as in C Programming) which allows you to combine different data types to store a particular type of record.
• It is somewhat similar to an Array. The only difference is that array is used to store collection of similar data types while structure can store collection of any type of data. Example: Structure is used to represent a record.
• Suppose you want to store record of Student which consists of student name, address, roll number and age. You can define a structure to hold this information.
• Suppose you want to keep track of your books in a library. You might want to track the following attributes about each book:
• Title
• Author
• Subject
• Book ID

Solved Example: 9257-01

Consider the following C declaration

struct {

short s[5];

union {

float y;

long z;

}u;

}t;

Assume that objects of type short, float and long occupy 2 bytes, 4 bytes and 8 bytes, respectively. The memory requirement for variable t, ignoring alignment considerations, is

A. 22 bytes

B. 18 bytes

C. 14 bytes

D. 10 bytes

Correct Answer: B

Learning Objectives:

• Understand the concept of arrays as a data structure used for storing collections of elements of the same data type.
• Differentiate between one-dimensional and multi-dimensional arrays.

Solved Example: 9970-01

Consider a 2-dimensional array x with 10 rows and 4 columns, with each element storing a value equivalent to the product of row number and column number. The array is stored in row-major format. If the first element x[0][0] occupies the memory location with address 1000 and each element occupies only one memory location, which all locations (in decimal) will be holding a value of 10?

A. 1018, 1019

B. 1022, 1041

C. 1017, 1036

D. 1000, 1399

Correct Answer: C

Solved Example: 9970-02

An algorithm performs $(\log N)^{\dfrac{1}{2}}$ find operations, N inserts operations, $(\log N)^{\dfrac{1}{2}}$ delete operations, and $(\log N)^{\dfrac{1}{2}}$ decrease - key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease - key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

A. Unsorted array

B. Min-heap

C. Sorted array

D. Sorted doubly linked list

Correct Answer: A