Data Structure (CS-303) Unit 1 Notes - RGPV

How unit 1 is examined

This unit covers C revision, data structure classification, ADTs, operations and asymptotic cost, arrays and the three linked lists. Classification, operations with cost, and circular linked lists carry the most marks.

Review of C programming language

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. C is a procedural, structured language in which a data structure is built from structures, pointers and dynamic memory.

Key points.

A struct groups variables of different types into one unit, which is how a list node is declared.
A pointer stores an address; *p reads the value and p->x reaches a structure member.
malloc(size) takes heap memory at run time, free(p) returns it, and NULL marks the end of a chain.

Introduction to Data Structure: Concepts of Data and Information

Definition. <mark>Data is a collection of raw facts and figures, while information is data that has been processed into a meaningful form that supports a decision.</mark>

Key points.

Data is unprocessed and has no meaning by itself; for example, the numbers 35, 42 and 58 are data.
Information is data given context; "the average mark of the class is 45" is information.
A data structure is a way of organising data in memory so that the required operations are efficient.
A polynomial such as $3x^2+5x+1$ is an ordered set of (coefficient, exponent) terms, stored as an array or a linked list.
An ADT is a logical description of data and operations, independent of implementation.

Asked: [7 marks] (Jun 2020) Define: i) Data and information ii) Abstract Data Types iii) Polynomials

Classification of Data structures

Definition. <mark>A data structure is a systematic way of organising and storing data in memory so that it can be accessed and modified efficiently through a defined set of operations.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 924 262" width="924" height="262" role="img" aria-label="Classification of data structures"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="373.3" y1="39" x2="137.8" y2="103"/><line class="e" x1="373.3" y1="39" x2="608.8" y2="103"/><line class="e" x1="137.8" y1="103" x2="31" y2="167"/><line class="e" x1="137.8" y1="103" x2="93.5" y2="167"/><line class="e" x1="137.8" y1="103" x2="165" y2="167"/><line class="e" x1="137.8" y1="103" x2="244.5" y2="167"/><line class="e" x1="608.8" y1="103" x2="463.5" y2="167"/><line class="e" x1="608.8" y1="103" x2="754" y2="167"/><line class="e" x1="463.5" y1="167" x2="327.5" y2="231"/><line class="e" x1="463.5" y1="167" x2="426" y2="231"/><line class="e" x1="463.5" y1="167" x2="524.5" y2="231"/><line class="e" x1="463.5" y1="167" x2="599.5" y2="231"/><line class="e" x1="754" y1="167" x2="671" y2="231"/><line class="e" x1="754" y1="167" x2="742.5" y2="231"/><line class="e" x1="754" y1="167" x2="837" y2="231"/><rect class="n" x="304.8" y="24" width="137" height="30" rx="8"/><text class="t" x="373.3" y="39" dy=".35em" text-anchor="middle">Data structures</text><rect class="n" x="92.3" y="88" width="91" height="30" rx="8"/><text class="t" x="137.8" y="103" dy=".35em" text-anchor="middle">Primitive</text><circle class="n" cx="31" cy="167" r="17"/><text class="t" x="31" y="167" dy=".35em" text-anchor="middle">int</text><rect class="n" x="64" y="152" width="59" height="30" rx="8"/><text class="t" x="93.5" y="167" dy=".35em" text-anchor="middle">float</text><rect class="n" x="139" y="152" width="52" height="30" rx="8"/><text class="t" x="165" y="167" dy=".35em" text-anchor="middle">char</text><rect class="n" x="207" y="152" width="75" height="30" rx="8"/><text class="t" x="244.5" y="167" dy=".35em" text-anchor="middle">pointer</text><rect class="n" x="547.8" y="88" width="122" height="30" rx="8"/><text class="t" x="608.8" y="103" dy=".35em" text-anchor="middle">Non-primitive</text><rect class="n" x="430" y="152" width="67" height="30" rx="8"/><text class="t" x="463.5" y="167" dy=".35em" text-anchor="middle">Linear</text><rect class="n" x="298" y="216" width="59" height="30" rx="8"/><text class="t" x="327.5" y="231" dy=".35em" text-anchor="middle">Array</text><rect class="n" x="373" y="216" width="106" height="30" rx="8"/><text class="t" x="426" y="231" dy=".35em" text-anchor="middle">Linked list</text><rect class="n" x="495" y="216" width="59" height="30" rx="8"/><text class="t" x="524.5" y="231" dy=".35em" text-anchor="middle">Stack</text><rect class="n" x="570" y="216" width="59" height="30" rx="8"/><text class="t" x="599.5" y="231" dy=".35em" text-anchor="middle">Queue</text><rect class="n" x="705" y="152" width="98" height="30" rx="8"/><text class="t" x="754" y="167" dy=".35em" text-anchor="middle">Non-linear</text><rect class="n" x="645" y="216" width="52" height="30" rx="8"/><text class="t" x="671" y="231" dy=".35em" text-anchor="middle">Tree</text><rect class="n" x="713" y="216" width="59" height="30" rx="8"/><text class="t" x="742.5" y="231" dy=".35em" text-anchor="middle">Graph</text><rect class="n" x="788" y="216" width="98" height="30" rx="8"/><text class="t" x="837" y="231" dy=".35em" text-anchor="middle">Hash table</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Classification of data structures</figcaption></figure>

Key points.

Primitive data structures are the basic types built into the language, namely integer, float, character and pointer, and machine instructions work on them directly.
Non-primitive data structures are derived from primitive ones and hold collections of values; they are divided into linear and non-linear.
In a linear structure the elements form a sequence, each has one predecessor and one successor, and they are traversed in a single pass; examples are array, linked list, stack and queue.
An array is a fixed-size block of same-type elements in contiguous memory, accessed by index in $O(1)$.
A linked list is a chain of nodes joined by pointers, so it grows and shrinks at run time.
Stack (LIFO) and queue (FIFO) are linear structures that restrict where insertion and deletion happen.
In a non-linear structure an element may connect to many others, so the data is not in a single sequence; a tree stores hierarchy and a graph stores general relations.

Answer frame. Open with the definition of a data structure; draw the classification tree; explain primitive then non-primitive, then linear (array, list, stack, queue) with one example each, then non-linear (tree, graph); close by saying the choice depends on the operations needed.

Asked: [7 marks] (Jun 2020, Dec 2020, Dec 2024, Dec 2025) What is a data structure? Explain various types / classifications of data structures in detail, with an example. Asked: [7 marks] (Dec 2025) Explain the classification of data structures in detail.

Abstract Data Types

Definition. <mark>An Abstract Data Type (ADT) is a logical model that defines a set of data values and the operations on them, without saying how they are stored or coded.</mark>

Key points.

An ADT separates the interface (what operations exist) from the implementation (how they work), which is abstraction.
The user calls operations only, so the implementation can change without changing the program that uses it (encapsulation).
Common ADTs are List, Stack, Queue, Tree and Graph, and each is defined by its operations.
Example, Stack ADT: data is an ordered collection of items; operations are push(x), pop(), peek(), isEmpty() and isFull(), all obeying LIFO. It can be built on an array or a linked list.
A data structure is the concrete implementation of an ADT in a programming language.

Basis	Array	Linked list
Memory	Static, contiguous	Dynamic, scattered nodes
Access	$O(1)$ by index	$O(n)$ by traversal
Insert/delete	$O(n)$ shifting	$O(1)$ once position is known
Overhead	None	Extra pointer per node
Size	Fixed, may waste space	Grows and shrinks on demand
Best for	Frequent random access	Frequent insertion and deletion

Answer frame. Open with the ADT definition; state interface versus implementation; give the Stack ADT with its operations; for the comparison question give the table and close with a trade-off sentence.

Asked: [7 marks] (Nov 2018, Jun 2023) Explain abstract data type with example. What are the different abstract data types? Explain. Asked: [7 marks] (Dec 2024) Compare and contrast the characteristics of arrays and linked lists as abstract data types.

Implementation aspects: Memory representation

Definition. Memory representation is how a data structure's elements are placed in main memory, either contiguously (sequential) or linked by pointers.

Key points.

Sequential representation stores elements in adjacent locations, so the address of any element is computed from the base address.
Linked representation stores elements in separate nodes anywhere in the heap and connects them with pointers.
Sequential storage gives fast access but costly insertion; linked storage gives cheap insertion but needs extra pointer memory.

Data structures operations and its cost estimation

Definition. <mark>Data structure operations are the basic actions performed on stored data, and cost estimation measures the time and space an operation needs as a function of input size $n$.</mark>

Key points.

Traversing visits every element exactly once, for example to print or sum all values.
Searching finds the location of a given value, by linear search in $O(n)$ or binary search in $O(\log n)$ on sorted data.
Insertion adds a new element at a given position; deletion removes an element and closes the gap.
Sorting arranges the elements in ascending or descending order.
Merging combines two sorted lists into one sorted list, and updating changes the value of an existing element.

Cost criteria. Cost is judged by time complexity (number of basic steps) and space complexity (extra memory used), taken for the best, average and worst case; the worst case is quoted in exams.

Asymptotic notation. Asymptotic analysis compares growth rates for large $n$, ignoring constants.

Big-O: $f(n)=O(g(n))$ if $f(n)\le c\,g(n)$ for all $n\ge n_0$ (upper bound).
Omega: $f(n)=\Omega(g(n))$ if $f(n)\ge c\,g(n)$ for all $n\ge n_0$ (lower bound).
Theta: $f(n)=\Theta(g(n))$ if $c_1 g(n)\le f(n)\le c_2 g(n)$ for all $n\ge n_0$ (tight bound).
Growth order: $1<\log n<n<n\log n<n^2<2^n$.
Example: $3n^2+5n+2=\Theta(n^2)$, taking $c_1=3$, $c_2=4$ and $n_0=6$.

Example (Dec 2023 loops).

Fragment	Work	Result
(i) two loops in a row	$N+M$	$O(N+M)$
(i) second loop to $N$	$N+N=2N$	$O(N)$
(ii) nested, then single	$N\cdot N+M$	$O(N^2+M)$

Sequential blocks add, nested blocks multiply, and the larger term dominates.

Recurrence (Nov 2019). $T(n)=2T(n/2)+n\log n$. Master theorem fails because $n\log n$ is only a log factor above $n^{\log_2 2}=n$. Recursion tree: level $i$ has $2^i$ nodes each costing $\frac{n}{2^i}\log\frac{n}{2^i}$, so the level costs $n(\log n-i)$. Summing over $i=0$ to $\log n-1$ gives $n\cdot\frac{\log n(\log n+1)}{2}$.

$$T(n)=\Theta(n\log^2 n)$$

Tournament tree. A tournament (winner) tree is a complete binary tree whose leaves are the items and each internal node holds the winner of its two children, so the root holds the overall smallest (or largest). Replacing the root's leaf and replaying its path costs $O(\log k)$, which makes it useful for k-way merging and selection. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-02" viewBox="0 0 360 198" width="360" height="198" role="img" aria-label="Winner tree for 8, 4, 6, 2 (smaller wins); root 2 is the minimum"><style>#dsfig-u1-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-02 .t{fill:#16181D;font-weight:500}#dsfig-u1-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-02 .dot{fill:#16181D}#dsfig-u1-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-02 .ah{fill:#454C5A}#dsfig-u1-02 .ah.hi{fill:#2340B8}#dsfig-u1-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-02 .e{stroke:#B1B7C3}html.dark #dsfig-u1-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-02 .t{fill:#E6E8ED}html.dark #dsfig-u1-02 .t.inv{fill:#0F1115}html.dark #dsfig-u1-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-02 .dot{fill:#E6E8ED}html.dark #dsfig-u1-02 .ann{fill:#8FA3FF}html.dark #dsfig-u1-02 .lbl{fill:#858D9C}html.dark #dsfig-u1-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-02 .ah{fill:#B1B7C3}html.dark #dsfig-u1-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="168" y1="39" x2="80" y2="103"/><line class="e" x1="168" y1="39" x2="256" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="124" y2="167"/><line class="e" x1="256" y1="103" x2="212" y2="167"/><line class="e" x1="256" y1="103" x2="300" y2="167"/><circle class="n" cx="168" cy="39" r="17"/><text class="t" x="168" y="39" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="212" cy="167" r="17"/><text class="t" x="212" y="167" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">2</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Winner tree for 8, 4, 6, 2 (smaller wins); root 2 is the minimum</figcaption></figure>

Answer frame. For operations: open with a one-line definition, list the six operations with a one-line example each, then the cost criteria. For asymptotic notation: define analysis, the three formal definitions, the growth order and one example. For loops and recurrence: write work per block, add or multiply, then state the bound.

Asked: [7 marks] (Nov 2019, Jun 2024) Describe asymptotic notation in detail. Asked: [7 marks] (May 2019, Nov 2022) Explain the common operations performed on data structures. Asked: [7 marks] (Nov 2019) Give the solution for the recurrence $T(n)=2T[n/2]+n\log n$. Asked: [7 marks] (May 2019) Short notes: i) common operations in data structure ii) tournament tree. Asked: [8 marks] (Dec 2023) Worst-case complexity of the code fragments: two loops in a row (and if the second goes to $N$), and a nested loop followed by a single loop. Asked: [7 marks] (Dec 2025) Define ADT, explain the operations on data structures and describe the criteria for cost estimation.

Introduction to linear data structures- Arrays

Definition. <mark>An array is a linear collection of a fixed number of same-type elements stored in contiguous memory locations and accessed by an index.</mark>

Key points.

A one-dimensional array int a[5] is a single row (subscripts 0 to 4), while a multi-dimensional array such as int m[3][4] is an array of arrays needing one subscript per dimension and used for matrices.
A multi-dimensional array is stored linearly in memory, row by row or column by column.
Access is $O(1)$ because the address is computed directly, but insertion and deletion are $O(n)$ because elements shift.
A static array has its size fixed at compile time, so it cannot grow and may waste space.
A dynamic array is allocated with malloc on the heap and has a capacity and a size; when full it doubles its capacity and copies the elements, so append is $O(1)$ amortized.

Formula. For a 1-D array, $\text{Addr}(A[i])=BA+w\,(i-LB)$. For a 3-D array $A[D_1][D_2][D_3]$ with zero-based indices, base address $BA$ and element size $w$:

$$\text{Row-major: } BA+w\big[(i\,D_2+j)\,D_3+k\big]$$ $$\text{Column-major: } BA+w\big[(k\,D_2+j)\,D_1+i\big]$$

Example: int A[3][4][5], $BA=1000$, $w=4$, element $A[1][2][3]$. Row-major: $1000+4[(1\cdot4+2)\cdot5+3]=1000+4\cdot33=\mathbf{1132}$.

Answer frame. Open with the array definition; give the 1-D and 2-D declarations; write the two address formulas with the variables named; work one numerical; for dynamic arrays contrast static and dynamic and end with amortized $O(1)$.

Asked: [7 marks] (May 2019) Explain various algorithms used in data structure. Also differentiate single and multiple dimensional array with example. Asked: [4 marks] (Dec 2023) What is ADT? Compute the addresses of a 3-D array in row and column major form. Asked: [7 marks] (Dec 2024) Describe a dynamic array and how it differs from a static array in memory management and flexibility.

Linked List: Representation of linked list in memory

Definition. <mark>A linked list is a linear collection of nodes in which each node holds a data field and a pointer to the next node, and the list is reached through a head pointer.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-03" viewBox="0 0 296 58" width="296" height="58" role="img" aria-label="Singly linked list; each node has a data field and a next pointer"><style>#dsfig-u1-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-03 .t{fill:#16181D;font-weight:500}#dsfig-u1-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-03 .dot{fill:#16181D}#dsfig-u1-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-03 .ah{fill:#454C5A}#dsfig-u1-03 .ah.hi{fill:#2340B8}#dsfig-u1-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-03 .e{stroke:#B1B7C3}html.dark #dsfig-u1-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-03 .t{fill:#E6E8ED}html.dark #dsfig-u1-03 .t.inv{fill:#0F1115}html.dark #dsfig-u1-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-03 .dot{fill:#E6E8ED}html.dark #dsfig-u1-03 .ann{fill:#8FA3FF}html.dark #dsfig-u1-03 .lbl{fill:#858D9C}html.dark #dsfig-u1-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-03 .ah{fill:#B1B7C3}html.dark #dsfig-u1-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><text class="ptr" x="14" y="29" dy=".35em" text-anchor="start">head</text><line class="e" x1="52" y1="29" x2="75" y2="29" marker-end="url(#ah3)"/><rect class="n" x="76" y="14" width="46" height="30" rx="3"/><text class="t" x="91" y="29" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="106" y1="14" x2="106" y2="44"/><circle class="dot" cx="114" cy="29" r="2.6"/><line class="e" x1="114" y1="29" x2="155" y2="29" marker-end="url(#ah3)"/><rect class="n" x="156" y="14" width="46" height="30" rx="3"/><text class="t" x="171" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="186" y1="14" x2="186" y2="44"/><circle class="dot" cx="194" cy="29" r="2.6"/><line class="e" x1="194" y1="29" x2="235" y2="29" marker-end="url(#ah3)"/><rect class="n" x="236" y="14" width="46" height="30" rx="3"/><text class="t" x="251" y="29" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="266" y1="14" x2="266" y2="44"/><line class="kd" x1="269" y1="41" x2="279" y2="17"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Singly linked list; each node has a data field and a next pointer</figcaption></figure>

Key points.

A node is struct node { int data; struct node *next; }; and each node is created with malloc.
The nodes are non-contiguous in memory; only the pointers give the order, unlike an array.
The head pointer holds the address of the first node, and the last node's next is NULL.
Memory can also be simulated with parallel arrays INFO[] and LINK[], where LINK[i] is the index of the next node, START is the first index and 0 or $-1$ is null.
Operations are traversal, search, insertion (beginning, end, position) and deletion.

Algorithm: insert at position pos.

Step 1: Create newNode with malloc; set newNode->data = x.
Step 2: If pos = 1: newNode->next = head; head = newNode; stop.
Step 3: Set temp = head; move temp forward pos-2 times.
Step 4: If temp = NULL, print "invalid position"; stop.
Step 5: newNode->next = temp->next; temp->next = newNode.

Example: inserting 25 at position 3 of 10, 20, 30 gives 10, 20, 25, 30.

Answer frame. Open with the definition; draw the node and head-to-NULL diagram; explain node structure, dynamic and parallel-array representations; give the insertion algorithm with the edge cases; close with one worked example.

Asked: [7 marks] (Nov 2022) How is a linked list represented in memory? Explain. Asked: [7 marks] (Jun 2023) What is a linked list? Explain its operations with examples. Asked: [7 marks] (Dec 2025) Describe the memory representation of a singly linked list and write an algorithm to insert a node at a specific position.

different implementation of linked list

Definition. <mark>Linked lists are implemented as singly, doubly or circular lists, and traversal visits every node once by following next pointers from the head until NULL.</mark>

Key points.

A singly list has one next pointer per node (forward only), a doubly list adds prev, and a circular list points the last node back to the first.
Traversal uses a temporary pointer so that head is never lost.

Algorithm: traversal.

Step 1: Set temp = head.
Step 2: While temp != NULL, repeat Steps 3 and 4.
Step 3: Print temp->data.
Step 4: temp = temp->next.
Step 5: Stop.

Trace on 10, 20, 30: temp = 10 (print), 20 (print), 30 (print), NULL (stop). Time is $O(n)$ and extra space is $O(1)$.

Answer frame. Open with the node structure and the head pointer; write the algorithm with the temp pointer; trace it on a three-node list; close with $O(n)$ time.

Asked: [7 marks] (Jun 2020, Dec 2024) Write an algorithm for traversing nodes in a single linked list. Explain with an example.

Circular linked list

Definition. <mark>A circular linked list is a linked list in which the link of the last node points back to the first node instead of NULL, so the list forms a closed ring.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-04" viewBox="0 0 296 80" width="296" height="80" role="img" aria-label="Circular singly linked list; the last node points back to the head"><style>#dsfig-u1-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-04 .t{fill:#16181D;font-weight:500}#dsfig-u1-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-04 .dot{fill:#16181D}#dsfig-u1-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-04 .ah{fill:#454C5A}#dsfig-u1-04 .ah.hi{fill:#2340B8}#dsfig-u1-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-04 .e{stroke:#B1B7C3}html.dark #dsfig-u1-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-04 .t{fill:#E6E8ED}html.dark #dsfig-u1-04 .t.inv{fill:#0F1115}html.dark #dsfig-u1-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-04 .dot{fill:#E6E8ED}html.dark #dsfig-u1-04 .ann{fill:#8FA3FF}html.dark #dsfig-u1-04 .lbl{fill:#858D9C}html.dark #dsfig-u1-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-04 .ah{fill:#B1B7C3}html.dark #dsfig-u1-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><text class="ptr" x="14" y="29" dy=".35em" text-anchor="start">head</text><line class="e" x1="52" y1="29" x2="75" y2="29" marker-end="url(#ah4)"/><rect class="n" x="76" y="14" width="46" height="30" rx="3"/><text class="t" x="91" y="29" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="106" y1="14" x2="106" y2="44"/><circle class="dot" cx="114" cy="29" r="2.6"/><line class="e" x1="114" y1="29" x2="155" y2="29" marker-end="url(#ah4)"/><rect class="n" x="156" y="14" width="46" height="30" rx="3"/><text class="t" x="171" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="186" y1="14" x2="186" y2="44"/><circle class="dot" cx="194" cy="29" r="2.6"/><line class="e" x1="194" y1="29" x2="235" y2="29" marker-end="url(#ah4)"/><rect class="n" x="236" y="14" width="46" height="30" rx="3"/><text class="t" x="251" y="29" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="266" y1="14" x2="266" y2="44"/><circle class="dot" cx="274" cy="29" r="2.6"/><path class="e" d="M274,29 V60 H99 V45" marker-end="url(#ah4)"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Circular singly linked list; the last node points back to the head</figcaption></figure>

Key points.

There is no NULL anywhere, so any node can be reached from any other node by following next pointers.
It may be singly circular (one next pointer) or doubly circular (prev and next, with first and last joined both ways).
The end of traversal is detected by returning to the start node, not by NULL.
Keeping a pointer last to the last node makes insertion at both ends $O(1)$, because last->next is the first node.
Operations are insertion at beginning or end, deletion from beginning or end, traversal and searching.
Applications are round-robin CPU scheduling, circular queues, multiplayer turn order and music playlists that repeat.

Algorithm: insertion and deletion (with last pointer).

Insert at beginning:
Step 1: Create newNode with data x.
Step 2: If last = NULL: last = newNode; newNode->next = newNode; stop.
Step 3: newNode->next = last->next; last->next = newNode.
Insert at end: do the same, then set last = newNode.
Delete from beginning:
Step 1: If last = NULL, print "underflow"; stop.
Step 2: temp = last->next.
Step 3: If temp = last: last = NULL. Else last->next = temp->next.
Step 4: free(temp).
Delete from end:
Step 1: If last = NULL, print "underflow"; stop.
Step 2: If last->next = last: free(last); last = NULL; stop.
Step 3: Find p, the node before last (walk from last->next).
Step 4: p->next = last->next; free(last); last = p.

Basis	Circular	Linear (singly)
Last node points to	First node	NULL
Traversal from	Any node	Head only
Insert at end	$O(1)$ with `last`	$O(n)$ without tail
Risk	Infinite loop if the stop test is wrong	None
Use	Round robin, circular queue	General storage

Advantages: continuous traversal and efficient queues. Disadvantages: complex pointer handling and risk of an infinite loop.

Answer frame. Open with the definition; draw the ring; list the operations with the algorithms above; give the comparison table and applications; close with the infinite-loop caution. For a short note, use the definition, diagram, two operations and applications.

Asked: [14 marks] (Dec 2025) Write short notes on any two: a) Circular Linked Lists b) Linear Probing and Chaining c) B+ Trees d) Dijkstra's shortest path algorithm Asked: [7 marks] (Nov 2018) Give the implementation of circular linked list. Also give its application. Asked: [7 marks] (Dec 2020) What is a circular linked list? State its advantages and disadvantages. Asked: [7 marks] (Jun 2020, Nov 2022) What are circular linked lists? What operations can you perform on them? Explain briefly. Asked: [7 marks] (Jun 2023, Jun 2024) Write an algorithm for insert and delete operations in a circular linked list.

doubly linked list

Definition. <mark>A doubly linked list is a linked list in which every node has three fields, a previous pointer, data and a next pointer, so it can be traversed in both directions.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-05" viewBox="0 0 344 58" width="344" height="58" role="img" aria-label="Doubly linked list; the first prev and the last next are NULL"><style>#dsfig-u1-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-05 .t{fill:#16181D;font-weight:500}#dsfig-u1-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-05 .dot{fill:#16181D}#dsfig-u1-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-05 .ah{fill:#454C5A}#dsfig-u1-05 .ah.hi{fill:#2340B8}#dsfig-u1-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-05 .e{stroke:#B1B7C3}html.dark #dsfig-u1-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-05 .t{fill:#E6E8ED}html.dark #dsfig-u1-05 .t.inv{fill:#0F1115}html.dark #dsfig-u1-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-05 .dot{fill:#E6E8ED}html.dark #dsfig-u1-05 .ann{fill:#8FA3FF}html.dark #dsfig-u1-05 .lbl{fill:#858D9C}html.dark #dsfig-u1-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-05 .ah{fill:#B1B7C3}html.dark #dsfig-u1-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><text class="ptr" x="14" y="29" dy=".35em" text-anchor="start">head</text><line class="e" x1="52" y1="29" x2="75" y2="29" marker-end="url(#ah5)"/><rect class="n" x="76" y="14" width="62" height="30" rx="3"/><line class="kd" x1="92" y1="14" x2="92" y2="44"/><text class="t" x="107" y="29" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="122" y1="14" x2="122" y2="44"/><line class="kd" x1="79" y1="41" x2="89" y2="17"/><circle class="dot" cx="130" cy="23.6" r="2.6"/><line class="e" x1="130" y1="23.6" x2="171" y2="23.6" marker-end="url(#ah5)"/><circle class="dot" cx="180" cy="34.4" r="2.6"/><line class="e" x1="180" y1="34.4" x2="139" y2="34.4" marker-end="url(#ah5)"/><rect class="n" x="172" y="14" width="62" height="30" rx="3"/><line class="kd" x1="188" y1="14" x2="188" y2="44"/><text class="t" x="203" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="218" y1="14" x2="218" y2="44"/><circle class="dot" cx="226" cy="23.6" r="2.6"/><line class="e" x1="226" y1="23.6" x2="267" y2="23.6" marker-end="url(#ah5)"/><circle class="dot" cx="276" cy="34.4" r="2.6"/><line class="e" x1="276" y1="34.4" x2="235" y2="34.4" marker-end="url(#ah5)"/><rect class="n" x="268" y="14" width="62" height="30" rx="3"/><line class="kd" x1="284" y1="14" x2="284" y2="44"/><text class="t" x="299" y="29" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="314" y1="14" x2="314" y2="44"/><line class="kd" x1="317" y1="41" x2="327" y2="17"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Doubly linked list; the first prev and the last next are NULL</figcaption></figure>

Key points.

The node is struct node { struct node *prev; int data; struct node *next; };.
Backward traversal is possible, and a node can be deleted knowing only its own address.
Each node needs an extra pointer, and every insert or delete must update both links.

Algorithm.

Insert at beginning:
Step 1: newNode->prev = NULL; newNode->next = head.
Step 2: If head != NULL: head->prev = newNode.
Step 3: head = newNode.
Insert at end:
Step 1: Walk temp to the last node.
Step 2: temp->next = newNode; newNode->prev = temp; newNode->next = NULL.
Delete node p:
Step 1: If p->prev != NULL: p->prev->next = p->next. Else head = p->next.
Step 2: If p->next != NULL: p->next->prev = p->prev.
Step 3: free(p).

Trace (Dec 2023). The function swaps prev and next of every node, so each link is reversed. The loop stops when current is NULL, and head is set to temp->prev, which is the old last node. For $1\leftrightarrow2\leftrightarrow3\leftrightarrow4\leftrightarrow5\leftrightarrow6$ the result is:

Output: 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1 (the list is reversed).

Answer frame. Open with the definition and node structure; draw the diagram; give insert then delete steps at beginning, end and position; close with the trade-off of two pointers versus two-way movement. For the trace, show the swap on one node and state the reversed list.

Asked: [7 marks] (Dec 2020) What is a doubly linked list? Write an algorithm to insert and delete a node in a doubly linked list. Asked: [4 marks] (Dec 2023) Given fun(struct node **head_ref) that swaps prev and next of each node, what is the modified list for $1<->2<->3<->4<->5<->6$?

Application of linked list: polynomial manipulation using linked list

Definition. A polynomial is stored as a linked list in which each node holds a coefficient, an exponent and a pointer to the next term, kept in decreasing order of exponent.

Key points.

The node is struct term { int coef, exp; struct term *next; }; so $5x^3+2x+7$ becomes (5,3) -> (2,1) -> (7,0).
To add two polynomials, compare the exponents of the current terms of both lists.
If the exponents are equal, add the coefficients into one result term; otherwise copy the term with the larger exponent and advance that list.
Leftover terms of the longer polynomial are copied, and the time is $O(m+n)$.

Last-minute revision

Data is raw facts; information is processed, meaningful data.
Primitive: int, float, char, pointer. Non-primitive: linear (array, list, stack, queue) and non-linear (tree, graph).
ADT gives the operations, not the implementation.
Operations: traverse, search, insert, delete, sort, merge, update.
Big-O is an upper bound, Omega a lower bound, Theta a tight bound.
Two loops in a row give $O(N+M)$; a nested loop plus a single loop gives $O(N^2+M)$.
$T(n)=2T(n/2)+n\log n$ gives $\Theta(n\log^2 n)$.
Row-major 3-D address $=BA+w[(iD_2+j)D_3+k]$; column-major $=BA+w[(kD_2+j)D_1+i]$.
Array access is $O(1)$; list access is $O(n)$; list insertion is $O(1)$ once the position is reached.
A circular list's last node points to the first; a doubly list has prev and next.
Reversing a doubly list swaps prev and next in every node.

Memory hooks

ADT: "what, not how".
Big-O = ceiling, Omega = floor, Theta = both.
Circular list = a ring; stop when you return to the start.
Doubly list = two-way street; update two links every time.

Coverage checklist

Review of C programming language: no past questions; struct, pointer, malloc covered.
Introduction to Data Structure: Concepts of Data and Information: Jun 2020 definitions.
Classification of Data structures: Q on types (Jun 2020, Dec 2020, Dec 2024, Dec 2025), classification (Dec 2025).
Abstract Data Types: ADT with example (Nov 2018, Jun 2023), array vs linked list (Dec 2024).
Implementation aspects: Memory representation: no past questions.
Data structures operations and its cost estimation: asymptotic notation, operations, recurrence, tournament tree, loop complexity, cost criteria.
Introduction to linear data structures- Arrays: May 2019 array types, Dec 2023 3-D addresses, Dec 2024 dynamic array.
Linked List: Representation of linked list in memory: Nov 2022, Jun 2023, Dec 2025.
different implementation of linked list: traversal (Jun 2020, Dec 2024).
Circular linked list: Nov 2018, Jun 2020, Dec 2020, Nov 2022, Jun 2023, Jun 2024, Dec 2025.
doubly linked list: Dec 2020 insert/delete, Dec 2023 reversal trace.
Application of linked list: polynomial manipulation using linked list: no past questions.

Account

Data Structure (CS-303) - Unit 1 Short Notes

How unit 1 is examined

Review of C programming language

Introduction to Data Structure: Concepts of Data and Information

Classification of Data structures

Abstract Data Types

Implementation aspects: Memory representation

Data structures operations and its cost estimation

Introduction to linear data structures- Arrays

Linked List: Representation of linked list in memory

different implementation of linked list

Circular linked list

doubly linked list

Application of linked list: polynomial manipulation using linked list

Last-minute revision

Memory hooks

Coverage checklist