Data Structures (AD-303) Unit 1 Notes - RGPV

How unit 1 is examined

Address numericals and linked list algorithms carry the marks.

Concepts of Data and Information

<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">Medium weight</span>

Definition. <mark>Data is a collection of raw, unprocessed facts and figures; information is data that has been processed, organised and given context so that it is meaningful for decisions.</mark> A data type tells the compiler a variable's kind of value, size and operations.

Key points.

In general data is numeric (integer or real), character or alphanumeric (letters, digits, symbols), or logical/boolean (true or false).
C data types are primitive or built-in (int, char, float, double, void), derived (arrays, pointers, functions) and user-defined (struct, union, enum, typedef).
Modifiers short, long, signed, unsigned change size or range.
int holds whole numbers (%d), char one character (%c), float and double real numbers of about 6 and 15 digits (%f, %lf).

Type	Bytes	Range (typical)
`char` / `unsigned char`	1	-128 to 127 / 0 to 255
`short` / `unsigned short`	2	-32,768 to 32,767 / 0 to 65,535
`int` / `unsigned int`	4 (2 in Turbo C)	-2,147,483,648 to 2,147,483,647 / 0 to 4,294,967,295
`long` / `unsigned long`	4 (Windows, 32-bit), 8 (64-bit Linux)	as `int` when 4 bytes
`long long` / `unsigned long long`	8	about $\pm 9.2\times10^{18}$ / 0 to $1.8\times10^{19}$
`float`	4	1.2E-38 to 3.4E+38, 6 digits
`double`	8	2.2E-308 to 1.8E+308, 15 digits
`long double`	10, 12 or 16	3.4E-4932 to 1.2E+4932
`void`	no size (`sizeof(void)` is invalid in standard C)	no value; functions returning nothing, `void *`
Basis	Data	Information
---	---	---
Nature	Raw facts, no context	Processed, meaningful
Dependency	Independent input	Depends on data
Form	Raw numbers, symbols	Reports, charts, summaries
Reliability	Unspecific, not decision-ready	Specific, reliable for decisions
Example	Marks 45, 62, 78	Average 61.67, result Pass

Answer frame. Data vs information: definitions, table, example. Types of data: define data, general types (point 1), the three C categories, size table.

Asked: [7 marks] (Nov 2022) Mention the types of data. Write all built-in data types in C. Asked: [7 marks] (Jun 2023) What is the difference between data and information? Give one example of each.

Classification of Data structures

Definition. <mark>A data structure is a particular way of organising and storing data in memory so that it can be accessed and modified efficiently.</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 810 262" width="810" 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="361.4" y1="39" x2="137.8" y2="103"/><line class="e" x1="361.4" y1="39" x2="585.1" y2="103"/><line class="e" x1="137.8" y1="103" x2="31" y2="167"/><line class="e" x1="137.8" y1="103" x2="90" y2="167"/><line class="e" x1="137.8" y1="103" x2="161.5" y2="167"/><line class="e" x1="137.8" y1="103" x2="244.5" y2="167"/><line class="e" x1="585.1" y1="103" x2="463.5" y2="167"/><line class="e" x1="585.1" y1="103" x2="706.8" 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="706.8" y1="167" x2="671" y2="231"/><line class="e" x1="706.8" y1="167" x2="742.5" y2="231"/><rect class="n" x="292.9" y="24" width="137" height="30" rx="8"/><text class="t" x="361.4" 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="52" height="30" rx="8"/><text class="t" x="90" y="167" dy=".35em" text-anchor="middle">char</text><rect class="n" x="132" y="152" width="59" height="30" rx="8"/><text class="t" x="161.5" y="167" dy=".35em" text-anchor="middle">float</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="524.1" y="88" width="122" height="30" rx="8"/><text class="t" x="585.1" 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="657.8" y="152" width="98" height="30" rx="8"/><text class="t" x="706.8" 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></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Classification of data structures</figcaption></figure>

Key points.

Primitive structures are machine types; non-primitive ones are linear or non-linear.
In a linear structure each element except the first and last has one predecessor and one successor: array, linked list, stack, queue.
In a non-linear structure an element links to many others: tree, graph.
A stack is LIFO: push and pop happen only at the top, like a pile of plates.
A queue is FIFO: enqueue at the rear, dequeue from the front, like a ticket line.
A tree has one root and each other node one parent (disk folders); a graph is vertices joined by edges (cities and roads).
Static structures are fixed at compile time (array), dynamic ones grow at run time (linked list); homogeneous ones hold one type, heterogeneous ones mix types (structure).

Basis	Array	Linked list
Memory	Contiguous	Scattered nodes joined by pointers
Size	Fixed (static)	Dynamic
Access	By index, $O(1)$	Sequential, $O(n)$
Insert/delete	$O(n)$, elements shift	$O(1)$ at a known position
Search	$O(n)$; $O(\log n)$ if sorted	$O(n)$
Memory use	Unused slots wasted	No unused slots, but a pointer per node

Answer frame. Types: define, draw the tree, explain linear and non-linear, then static/dynamic. Differentiate: the table, closing "array suits fast access, list suits frequent insert/delete".

Asked: [7 marks] (Nov 2022, Dec 2025) What do you mean by data structure and mention its types? Asked: [7 marks] (Jun 2024) Differentiate array and linked list. 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 mathematical model of a data structure that specifies the data values and the operations on them, without saying how they are implemented.</mark>

Key points.

An ADT gives the set of values and the operations, each with inputs, output, pre-condition (true before) and post-condition (true after).
The specification (what) is separate from the implementation (how), and users reach the data only through the operations, so the implementation can change freely.
Stack ADT: push(S,x) adds x, pre not full; pop(S) removes and returns the top, pre not empty; peek(S) returns the top unchanged; isEmpty(S)/isFull(S) return true or false.
Operations are traversal, insertion, deletion, searching, sorting and merging; cost is time and space: array access $O(1)$, insert/delete $O(n)$, search $O(n)$, push/pop $O(1)$, list insert at head $O(1)$.

Example (Queue ADT). enqueue(Q,x): pre Q not full; post x at rear. dequeue(Q): pre Q not empty; post front removed and returned. front(Q): pre Q not empty; post front returned. isEmpty(Q): true if size is 0.

Answer frame. Definition, Queue ADT, specification versus implementation; Dec 2025: add operations and cost.

Asked: [7 marks] (Jun 2023, Jun 2024) What is Abstract data type? Explain with the help of example. Asked: [7 marks] (Dec 2025) Define Abstract Data Types (ADT). Explain the different operations performed on data structures and describe the criteria for cost estimation.

Implementation aspects: Memory representation

Definition. <mark>A two-dimensional array is stored in memory as a single contiguous block, either row by row (row-major) or column by column (column-major).</mark>

Key points.

Row-major order stores row 1 completely, then row 2; C uses it. Column-major stores column by column; FORTRAN uses it.
For an $m \times n$ array with lower bounds $L_r,L_c$, base $BA$ and element size $W$: row-major $\text{LOC}(A[i][j])=BA+W\,[(i-L_r)\,n+(j-L_c)]$.
Column-major $\text{LOC}(A[i][j])=BA+W\,[(j-L_c)\,m+(i-L_r)]$.
One-dimensional: $\text{LOC}(A[k])=BA+W(k-LB)$, with $UB-LB+1$ elements.

Example. $A[1..3,1..4]$, $BA=100$, $W=2$, $A[2][3]$: row-major $100+2[4+2]=$ 112; column-major $100+2[6+1]=$ 114.

Asked: [7 marks] (Jun 2023) How to represent 2-D array in memory? Explain with the help of example.

Data structures operations and its cost estimation

Definition. <mark>An algorithm is a finite, step-by-step procedure that takes input and produces the required output; its efficiency is measured by the time and space it needs as the input size $n$ grows.</mark>

Key points.

Characteristics: input, output, definiteness (clear steps), finiteness, effectiveness (basic steps), correctness, generality (solves every instance).
Criteria for cost estimation: time (count of basic operations), space (auxiliary memory), input size $n$, best/average/worst case, and order of growth, which keeps the estimate machine-independent.
Best, average and worst case are the fewest, expected and most steps for size $n$: linear search takes 1, about $n/2$ and $n$ comparisons. For $n=1024$ that is up to 1024, $O(n)$, against about $\log_2 1024+1=11$ for binary search on sorted data, $O(\log n)$.
Big-Oh $f(n)=O(g(n))$ if $f(n) \le c\,g(n)$ for all $n \ge n_0$: an upper bound.
Big-Omega $f(n)=\Omega(g(n))$ if $f(n) \ge c\,g(n)$ for all $n \ge n_0$: a lower bound.
Big-Theta: $c_1 g(n) \le f(n) \le c_2 g(n)$, a tight bound.
Growth: $1<\log n<n<n\log n<n^2<2^n$.

Proof. $3n+2 \le 4n$ for $n \ge 2$, so $c=4$, $n_0=2$.

Frequency count. for (i=0;i<n;i++) sum += a[i]; costs init 1, test $n+1$, increment $n$, body $n$: $3n+2$, $O(n)$.

Space example. An iterative sum uses one variable, $O(1)$ extra space; a recursive sum(n) keeps $n$ stack frames, $O(n)$.

Big-O           Omega           Theta
|     c.g       |     f         |     c2.g
|    / f        |    / c.g      |    / f
|   /./         |   /./         |   /./c1.g
|__/_:___ n     |__/_:___ n     |__/_:___ n
     n0              n0              n0
f<=c.g          f>=c.g          c1.g<=f<=c2.g

Formula. Master theorem $T(n)=aT(n/b)+f(n)$: if $f(n)=\Theta(n^{\log_b a}\log^k n)$ then $T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$.

Example. $T(n)=2T(n/2)+n\log n$: $a=b=2$, $n^{\log_2 2}=n$, $f(n)=n\log^1 n$, $k=1$, so $T(n)=\Theta(n\log^2 n)$.

Answer frame. Efficiency: time and space, cases, notations, proof, growth chain. Recurrence: $a,b,f(n)$, $n^{\log_b a}$, case, answer.

Pitfall: Writing "Big-O means worst case"; the notations are bounds, and any bound applies to any case (linear search: worst $\Theta(n)$, best $\Theta(1)$).

Asked: [7 marks] (Nov 2022, Jun 2024) Demonstrate the efficiency of an algorithm. How to measure the complexity of an algorithm, also discuss various types of notation for this purpose? Asked: [7 marks] (Dec 2022) Give the solution for following Recursion: $T(n)=2T[n/2]+n \log n$. Asked: [7 marks] (Nov 2022) What do you mean by an algorithm? Write the criteria and characteristics of an algorithm.

Introduction to linear data structures - Arrays

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

Key points.

Address formulas give $O(1)$ access; middle insertion or deletion shifts elements, $O(n)$.
Overflow is inserting into a full array (n<mark>MAX); underflow is deleting from an empty one (n</mark>0).
Compaction shifts live elements together after deletions so free space becomes one block; it costs $O(n)$ and changes element addresses.
A sparse matrix is mostly zeros; the triplet form stores only (row, column, value) of non-zeros after a header (rows, columns, count).
Lower triangular: $a_{ij}=0$ for $i<j$; upper triangular: $a_{ij}=0$ for $i>j$. The non-zero triangle fits in $n(n+1)/2$ cells of a 1-D array.
The other sparse form is a linked list of nodes struct SNode { int row, col, val; struct SNode *next; };. Column-major, 0-indexed: upper $BA+W[j(j+1)/2+i]$; lower $BA+W[jn-j(j-1)/2+(i-j)]$.
Row-major, 0-indexed: lower $BA+W[i(i+1)/2+j]$; upper $BA+W[i\,n-i(i-1)/2+(j-i)]$. Lower, 1-based: $BA+W[i(i-1)/2+(j-1)]$.

Insert(pos, x): Step 1: If n==MAX, "overflow"; stop. Step 2: For i=n-1 down to pos, A[i+1]=A[i]. Step 3: A[pos]=x; n++.
Delete(pos): Step 1: If n==0, "underflow"; stop. Step 2: For i=pos to n-2, A[i]=A[i+1]. Step 3: n--.

Example (sparse, 0-indexed). $\begin{bmatrix}0&0&3&0\\0&0&0&0\\5&0&0&7\\0&2&0&0\end{bmatrix}$: header (4,4,4), then (0,2,3), (2,0,5), (2,3,7), (3,1,2).

Example 1 (Dec 2023). $A[-100:100,-5:50]$, $BA=10$, $W=4$, row-major, $A[99,49]$: $N=50-(-5)+1=56$; $i-L_r=199$, $j-L_c=54$; offset $199\times 56+54=11198$; $10+4\times 11198$ = 44802.

Example 2 (Nov 2022). Column-major $\text{LOC}(A[i,j])=Base+w[m(j-LB_2)+(i-LB_1)]$. Sizes: AAA 46, BBB 16, CCC 8. Base 300, $w=4$: AAA[15] $=340$, AAA[35] $=420$, AAA[55] $=500$ (outside 5:50).

Example (triangular, 4×4, 0-indexed, row-major, $BA=100$, $W=2$). Lower: rows $0..i-1$ hold $1+2+\dots+i=i(i+1)/2$ elements, then $j$ more, so $A[3][2]=100+2(6+2)=$ 116. Upper: row $k$ holds $n-k$ elements, so $A[1][3]=100+2(4-0+2)=$ 112.

Example 3 (Dec 2023, 3-D, row-major). $A(-2{:}2,2{:}22)$: lengths 5, 21, so 105 elements. $B(1{:}8,-5{:}5,-10{:}5)$: lengths 8, 11, 16, so 1408. $B[3,3,3]$: $E_1=3-1=2$, $E_2=3+5=8$, $E_3=3+10=13$; $500+2[(2\times11+8)\times16+13]=500+2\times493=$ 1486.

Answer frame. Numerical: Given, formula, working, bold address. Sparse: triplets, formulas.

Pitfall: Using the upper bound instead of $N=UB-LB+1$, or forgetting the lower bound.

Asked: [5 marks] (Dec 2023) 2D array $A[-100:100,-5:50]$: address of $A[99,49]$, base 10, 4 bytes per element, row-major. Asked: [7 marks] (Nov 2022) Column-major formula for $m \times n$; counts of AAA[5:50], BBB[-5:10], CCC[1:8]; addresses of AAA[15], AAA[35], AAA[55] (base 300, $w=4$). Asked: [7 marks] (Dec 2023) A(-2:2, 2:22), B(1:8, -5:5, -10:5) row-major: lengths, element counts, effective indices, address of B[3,3,3] (base 500, W=2). Asked: [7 marks] (Jun 2023) Differentiate array and linked list. Asked: [7 marks] (Jun 2024) What are sparse matrices? Explain their representation, upper and lower triangular forms, a space-efficient representation and its address formulas. Asked: [7 marks] (Jun 2024) Write a note on Compaction, overflow and underflow in array term.

Linked List: Representation of linked list in memory

Definition. <mark>A singly 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 last node points to NULL.</mark>

Diagram.

head = 1000
[1000: 10 | 2050] -> [2050: 20 | 1300] -> [1300: 30 | NULL]

Key points.

Node: struct Node { int data; struct Node *next; };.
malloc places nodes anywhere; only the next fields give the order, and head holds the first address (empty list: NULL).
Advantages: run-time size, no shifting.
Applications: a polynomial keeps one node per term, a stack or queue pushes and pops at the list ends, an adjacency list keeps one list of neighbours per vertex, and dynamic memory management keeps free blocks on a free (available-space) list. Disadvantages: no random access, a pointer per node.

Step 1: head=tail=NULL.
Step 2: For each x, allocate n; if head is NULL, head=tail=n, else tail->next=n, tail=n.
Step 3: t=head; while t, print t->data, t=t->next.

#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main(void) {
    struct Node *head=NULL, *tail=NULL, *n;
    int x;
    while (scanf("%d", &x)==1) {            // input loop, stop at EOF
        n=malloc(sizeof *n); n->data=x; n->next=NULL;
        if (!head) head=tail=n; else { tail->next=n; tail=n; }
    }
    for (n=head; n; n=n->next) printf("%d -> ", n->data);
    printf("NULL\n");                          // 5 -> 6 -> 7 -> NULL
    return 0;
}

Worked cases (list above, new node n). pos 1: n->next=1000, head = n. pos 3 (middle): p makes 1 move to 2050 (node 20); n->next=1300, 2050's next = n. pos 4 (end): p makes 2 moves to 1300 (node 30); n->next=NULL, 1300's next = n. pos 5 or more: p becomes NULL, "invalid position".

Insert at position pos.

Step 1: If pos<1, print "invalid position"; stop.
Step 2: Create n. If pos=1, n->next=head, head=n; stop.
Step 3: Move p from head pos-2 times; if p is NULL, print "invalid position"; stop.
Step 4: n->next=p->next, then p->next=n.

Answer frame. Define, address diagram, node, advantages, algorithm, program, $O(n)$.

Asked: [7 marks] (Nov 2022) What is a singly linked list? Write its advantage and application and explain its node structure. Write the algorithm and program in C to create and traverse a singly linked list. Asked: [7 marks] (Dec 2025) Describe the memory representation of a singly linked list. Write an algorithm to insert a node at a specific position in a linked list.

Different implementation of linked list

Definition. <mark>The operations on a linked list are creation, traversal, counting, searching, updating, insertion, deletion, reversing, sorting and merging.</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-02" viewBox="0 0 430 106" width="430" height="106" role="img" aria-label="Insert 30 after 20"><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><text class="ptr" x="14" y="29" dy=".35em" text-anchor="start">Before</text><line class="e" x1="67" y1="29" x2="90" y2="29" marker-end="url(#ah2)"/><rect class="n" x="91" y="14" width="93" height="30" rx="3"/><text class="t" x="129.5" y="29" dy=".35em" text-anchor="middle">head: 10</text><line class="kd" x1="168" y1="14" x2="168" y2="44"/><circle class="dot" cx="176" cy="29" r="2.6"/><line class="e" x1="176" y1="29" x2="217" y2="29" marker-end="url(#ah2)"/><rect class="n" x="218" y="14" width="46" height="30" rx="3"/><text class="t" x="233" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="248" y1="14" x2="248" y2="44"/><circle class="dot" cx="256" cy="29" r="2.6"/><line class="e" x1="256" y1="29" x2="297" y2="29" marker-end="url(#ah2)"/><rect class="n" x="298" y="14" width="46" height="30" rx="3"/><text class="t" x="313" y="29" dy=".35em" text-anchor="middle">40</text><line class="kd" x1="328" y1="14" x2="328" y2="44"/><line class="kd" x1="331" y1="41" x2="341" y2="17"/><text class="ptr" x="14" y="77" dy=".35em" text-anchor="start">After</text><line class="e" x1="59" y1="77" x2="82" y2="77" marker-end="url(#ah2)"/><rect class="n" x="83" y="62" width="93" height="30" rx="3"/><text class="t" x="121.5" y="77" dy=".35em" text-anchor="middle">head: 10</text><line class="kd" x1="160" y1="62" x2="160" y2="92"/><circle class="dot" cx="168" cy="77" r="2.6"/><line class="e" x1="168" y1="77" x2="209" y2="77" marker-end="url(#ah2)"/><rect class="n" x="210" y="62" width="46" height="30" rx="3"/><text class="t" x="225" y="77" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="240" y1="62" x2="240" y2="92"/><circle class="dot" cx="248" cy="77" r="2.6"/><line class="e" x1="248" y1="77" x2="289" y2="77" marker-end="url(#ah2)"/><rect class="n hi" x="290" y="62" width="46" height="30" rx="3"/><text class="t" x="305" y="77" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="320" y1="62" x2="320" y2="92"/><circle class="dot" cx="328" cy="77" r="2.6"/><line class="e" x1="328" y1="77" x2="369" y2="77" marker-end="url(#ah2)"/><rect class="n" x="370" y="62" width="46" height="30" rx="3"/><text class="t" x="385" y="77" dy=".35em" text-anchor="middle">40</text><line class="kd" x1="400" y1="62" x2="400" y2="92"/><line class="kd" x1="403" y1="89" x2="413" y2="65"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Insert 30 after 20</figcaption></figure>

<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 507 106" width="507" height="106" role="img" aria-label="new->next = head, then head = new"><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">Before</text><line class="e" x1="67" y1="29" x2="90" y2="29" marker-end="url(#ah3)"/><rect class="n" x="91" y="14" width="93" height="30" rx="3"/><text class="t" x="129.5" y="29" dy=".35em" text-anchor="middle">head: 10</text><line class="kd" x1="168" y1="14" x2="168" y2="44"/><circle class="dot" cx="176" cy="29" r="2.6"/><line class="e" x1="176" y1="29" x2="217" y2="29" marker-end="url(#ah3)"/><rect class="n" x="218" y="14" width="46" height="30" rx="3"/><text class="t" x="233" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="248" y1="14" x2="248" y2="44"/><line class="kd" x1="251" y1="41" x2="261" y2="17"/><rect class="n" x="14" y="62" width="319" height="30" rx="3"/><text class="t" x="165.5" y="77" dy=".35em" text-anchor="middle">After insert 5 at beginning: head: *5</text><line class="kd" x1="317" y1="62" x2="317" y2="92"/><circle class="dot" cx="325" cy="77" r="2.6"/><line class="e" x1="325" y1="77" x2="366" y2="77" marker-end="url(#ah3)"/><rect class="n" x="367" y="62" width="46" height="30" rx="3"/><text class="t" x="382" y="77" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="397" y1="62" x2="397" y2="92"/><circle class="dot" cx="405" cy="77" r="2.6"/><line class="e" x1="405" y1="77" x2="446" y2="77" marker-end="url(#ah3)"/><rect class="n" x="447" y="62" width="46" height="30" rx="3"/><text class="t" x="462" y="77" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="477" y1="62" x2="477" y2="92"/><line class="kd" x1="480" y1="89" x2="490" y2="65"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">new->next = head, then head = new</figcaption></figure> <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 380 106" width="380" height="106" role="img" aria-label="p stops at 20, free(p->next)"><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">Before</text><line class="e" x1="67" y1="29" x2="90" y2="29" marker-end="url(#ah4)"/><rect class="n" x="91" y="14" width="93" height="30" rx="3"/><text class="t" x="129.5" y="29" dy=".35em" text-anchor="middle">head: 10</text><line class="kd" x1="168" y1="14" x2="168" y2="44"/><circle class="dot" cx="176" cy="29" r="2.6"/><line class="e" x1="176" y1="29" x2="217" y2="29" marker-end="url(#ah4)"/><rect class="n" x="218" y="14" width="46" height="30" rx="3"/><text class="t" x="233" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="248" y1="14" x2="248" y2="44"/><circle class="dot" cx="256" cy="29" r="2.6"/><line class="e" x1="256" y1="29" x2="297" y2="29" marker-end="url(#ah4)"/><rect class="n" x="298" y="14" width="46" height="30" rx="3"/><text class="t" x="313" y="29" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="328" y1="14" x2="328" y2="44"/><line class="kd" x1="331" y1="41" x2="341" y2="17"/><rect class="n" x="14" y="62" width="272" height="30" rx="3"/><text class="t" x="142" y="77" dy=".35em" text-anchor="middle">After delete from end: head: 10</text><line class="kd" x1="270" y1="62" x2="270" y2="92"/><circle class="dot" cx="278" cy="77" r="2.6"/><line class="e" x1="278" y1="77" x2="319" y2="77" marker-end="url(#ah4)"/><rect class="n" x="320" y="62" width="46" height="30" rx="3"/><text class="t" x="335" y="77" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="350" y1="62" x2="350" y2="92"/><line class="kd" x1="353" y1="89" x2="363" y2="65"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">p stops at 20, free(p->next)</figcaption></figure>

Key points.

Insert at beginning: new->next=head; head=new;, $O(1)$; at end: walk to the last node, last->next=new;, $O(n)$.
Insert after prev: new->next=prev->next; prev->next=new; in this order, or the rest is lost.
Delete first: temp=head; head=head->next; free(temp);. Delete a value: find its predecessor, pred->next=node->next, free it.
Delete at end: if head->next is NULL, free head, set it NULL; else walk p to the second-last node, free(p->next); p->next=NULL;.
Traverse, count, search and update each walk the nodes to NULL, $O(n)$.
Reverse with three pointers: prev=NULL, curr=head; while curr: next=curr->next; curr->next=prev; prev=curr; curr=next;; then head=prev.
Merge: if A is empty the result is B; else walk p to A's last node, p->next=B.
Sort: for each p and later q, swap data if p->data>q->data ($O(n^2)$).

void insertAfter(struct Node *prev, int x) {
    if (!prev) { printf("Previous node is NULL\n"); return; }
    struct Node *n=malloc(sizeof *n);
    n->data=x; n->next=prev->next; prev->next=n;
}

Answer frame. Operations one line each, the figures, three insertion cases.

Asked: [7 marks] (Nov 2022, Jun 2024) Explore all types of operations that can be performed on a linked list. Asked: [7 marks] (Dec 2024) Explain the insertion operation in linked list. How nodes are inserted after a specified node?

Circular linked list

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

<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 296 80" width="296" height="80" role="img" aria-label="Circular list"><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="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(#ah5)"/><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(#ah5)"/><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(#ah5)"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Circular list</figcaption></figure>

Key points.

Any node can be the start; traversal stops on returning to it, with while (p->next!=head).
A last-node pointer makes insertion at both ends $O(1)$; it suits round-robin scheduling.

Doubly linked list, etc

Definition. <mark>A doubly linked list is a linked list in which each node has three fields, prev, data and next, 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-06" viewBox="0 0 344 58" width="344" height="58" role="img" aria-label="Doubly linked list; each node is [prev|data|next]"><style>#dsfig-u1-06 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-06 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-06 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-06 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-06 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-06 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-06 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-06 .t{fill:#16181D;font-weight:500}#dsfig-u1-06 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-06 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-06 .dot{fill:#16181D}#dsfig-u1-06 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-06 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-06 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-06 .ah{fill:#454C5A}#dsfig-u1-06 .ah.hi{fill:#2340B8}#dsfig-u1-06 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-06 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-06 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-06 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-06 .e{stroke:#B1B7C3}html.dark #dsfig-u1-06 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-06 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-06 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-06 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-06 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-06 .t{fill:#E6E8ED}html.dark #dsfig-u1-06 .t.inv{fill:#0F1115}html.dark #dsfig-u1-06 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-06 .dot{fill:#E6E8ED}html.dark #dsfig-u1-06 .ann{fill:#8FA3FF}html.dark #dsfig-u1-06 .lbl{fill:#858D9C}html.dark #dsfig-u1-06 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-06 .ah{fill:#B1B7C3}html.dark #dsfig-u1-06 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-06 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-06 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-06 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" 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="ahh6" 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(#ah6)"/><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(#ah6)"/><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(#ah6)"/><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(#ah6)"/><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(#ah6)"/><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; each node is [prev|data|next]</figcaption></figure>

Key points.

It traverses forward by next and backward by prev (from tail); a singly list only goes forward, so reverse traversal or a backward search must re-scan from the head.
Given the node's address, a doubly list deletes in $O(1)$ (prev gives the predecessor, code below); a singly list must scan from the head for the predecessor, $O(n)$.
Disadvantages: an extra pointer per node and more updates.

void delDLL(struct Node *node) {   // doubly: O(1)
    if (!node) return;
    if (node->prev) node->prev->next=node->next; else head=node->next;  // head
    if (node->next) node->next->prev=node->prev; else tail=node->prev;  // last/only
    free(node);
}

Insert at beginning.

Step 1: Create n, n->prev=NULL, n->next=head.
Step 2: If head!=NULL, head->prev=n.
Step 3: head=n.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-07" viewBox="0 0 398 106" width="398" height="106" role="img" aria-label="Insert 5 at beginning. Changed: 5.prev = NULL, 5.next = 10, 10.prev = 5, head = 5"><style>#dsfig-u1-07 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-07 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-07 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-07 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-07 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-07 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-07 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-07 .t{fill:#16181D;font-weight:500}#dsfig-u1-07 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-07 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-07 .dot{fill:#16181D}#dsfig-u1-07 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-07 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-07 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-07 .ah{fill:#454C5A}#dsfig-u1-07 .ah.hi{fill:#2340B8}#dsfig-u1-07 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-07 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-07 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-07 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-07 .e{stroke:#B1B7C3}html.dark #dsfig-u1-07 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-07 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-07 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-07 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-07 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-07 .t{fill:#E6E8ED}html.dark #dsfig-u1-07 .t.inv{fill:#0F1115}html.dark #dsfig-u1-07 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-07 .dot{fill:#E6E8ED}html.dark #dsfig-u1-07 .ann{fill:#8FA3FF}html.dark #dsfig-u1-07 .lbl{fill:#858D9C}html.dark #dsfig-u1-07 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-07 .ah{fill:#B1B7C3}html.dark #dsfig-u1-07 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-07 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-07 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-07 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" 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="ahh7" 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">Before</text><line class="e" x1="67" y1="29" x2="90" y2="29" marker-end="url(#ah7)"/><rect class="n" x="91" y="14" width="109" height="30" rx="3"/><line class="kd" x1="107" y1="14" x2="107" y2="44"/><text class="t" x="145.5" y="29" dy=".35em" text-anchor="middle">head: 10</text><line class="kd" x1="184" y1="14" x2="184" y2="44"/><line class="kd" x1="94" y1="41" x2="104" y2="17"/><circle class="dot" cx="192" cy="23.6" r="2.6"/><line class="e" x1="192" y1="23.6" x2="233" y2="23.6" marker-end="url(#ah7)"/><circle class="dot" cx="242" cy="34.4" r="2.6"/><line class="e" x1="242" y1="34.4" x2="201" y2="34.4" marker-end="url(#ah7)"/><rect class="n" x="234" y="14" width="62" height="30" rx="3"/><line class="kd" x1="250" y1="14" x2="250" y2="44"/><text class="t" x="265" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="280" y1="14" x2="280" y2="44"/><line class="kd" x1="283" y1="41" x2="293" y2="17"/><text class="ptr" x="14" y="77" dy=".35em" text-anchor="start">After</text><line class="e" x1="59" y1="77" x2="82" y2="77" marker-end="url(#ah7)"/><rect class="n" x="83" y="62" width="109" height="30" rx="3"/><line class="kd" x1="99" y1="62" x2="99" y2="92"/><text class="t" x="137.5" y="77" dy=".35em" text-anchor="middle">head: *5</text><line class="kd" x1="176" y1="62" x2="176" y2="92"/><line class="kd" x1="86" y1="89" x2="96" y2="65"/><circle class="dot" cx="184" cy="71.6" r="2.6"/><line class="e" x1="184" y1="71.6" x2="225" y2="71.6" marker-end="url(#ah7)"/><circle class="dot" cx="234" cy="82.4" r="2.6"/><line class="e" x1="234" y1="82.4" x2="193" y2="82.4" marker-end="url(#ah7)"/><rect class="n" x="226" y="62" width="62" height="30" rx="3"/><line class="kd" x1="242" y1="62" x2="242" y2="92"/><text class="t" x="257" y="77" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="272" y1="62" x2="272" y2="92"/><circle class="dot" cx="280" cy="71.6" r="2.6"/><line class="e" x1="280" y1="71.6" x2="321" y2="71.6" marker-end="url(#ah7)"/><circle class="dot" cx="330" cy="82.4" r="2.6"/><line class="e" x1="330" y1="82.4" x2="289" y2="82.4" marker-end="url(#ah7)"/><rect class="n" x="322" y="62" width="62" height="30" rx="3"/><line class="kd" x1="338" y1="62" x2="338" y2="92"/><text class="t" x="353" y="77" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="368" y1="62" x2="368" y2="92"/><line class="kd" x1="371" y1="89" x2="381" y2="65"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Insert 5 at beginning. Changed: 5.prev = NULL, 5.next = 10, 10.prev = 5, head = 5</figcaption></figure>

Delete from end.

Step 1: If head is NULL, print "underflow"; stop.
Step 2: Move p to the last node.
Step 3: If p->prev is NULL, head=NULL; else p->prev->next=NULL. free(p).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-08" viewBox="0 0 406 106" width="406" height="106" role="img" aria-label="Delete from end. Changed: 20.next = NULL (tail = 20), node 30 freed"><style>#dsfig-u1-08 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-08 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-08 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-08 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-08 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-08 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-08 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-08 .t{fill:#16181D;font-weight:500}#dsfig-u1-08 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-08 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-08 .dot{fill:#16181D}#dsfig-u1-08 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-08 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-08 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-08 .ah{fill:#454C5A}#dsfig-u1-08 .ah.hi{fill:#2340B8}#dsfig-u1-08 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-08 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-08 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-08 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-08 .e{stroke:#B1B7C3}html.dark #dsfig-u1-08 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-08 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-08 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-08 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-08 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-08 .t{fill:#E6E8ED}html.dark #dsfig-u1-08 .t.inv{fill:#0F1115}html.dark #dsfig-u1-08 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-08 .dot{fill:#E6E8ED}html.dark #dsfig-u1-08 .ann{fill:#8FA3FF}html.dark #dsfig-u1-08 .lbl{fill:#858D9C}html.dark #dsfig-u1-08 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-08 .ah{fill:#B1B7C3}html.dark #dsfig-u1-08 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-08 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-08 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-08 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" 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="ahh8" 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">Before</text><line class="e" x1="67" y1="29" x2="90" y2="29" marker-end="url(#ah8)"/><rect class="n" x="91" y="14" width="109" height="30" rx="3"/><line class="kd" x1="107" y1="14" x2="107" y2="44"/><text class="t" x="145.5" y="29" dy=".35em" text-anchor="middle">head: 10</text><line class="kd" x1="184" y1="14" x2="184" y2="44"/><line class="kd" x1="94" y1="41" x2="104" y2="17"/><circle class="dot" cx="192" cy="23.6" r="2.6"/><line class="e" x1="192" y1="23.6" x2="233" y2="23.6" marker-end="url(#ah8)"/><circle class="dot" cx="242" cy="34.4" r="2.6"/><line class="e" x1="242" y1="34.4" x2="201" y2="34.4" marker-end="url(#ah8)"/><rect class="n" x="234" y="14" width="62" height="30" rx="3"/><line class="kd" x1="250" y1="14" x2="250" y2="44"/><text class="t" x="265" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="280" y1="14" x2="280" y2="44"/><circle class="dot" cx="288" cy="23.6" r="2.6"/><line class="e" x1="288" y1="23.6" x2="329" y2="23.6" marker-end="url(#ah8)"/><circle class="dot" cx="338" cy="34.4" r="2.6"/><line class="e" x1="338" y1="34.4" x2="297" y2="34.4" marker-end="url(#ah8)"/><rect class="n hi" x="330" y="14" width="62" height="30" rx="3"/><line class="kd" x1="346" y1="14" x2="346" y2="44"/><text class="t" x="361" y="29" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="376" y1="14" x2="376" y2="44"/><line class="kd" x1="379" y1="41" x2="389" y2="17"/><text class="ptr" x="14" y="77" dy=".35em" text-anchor="start">After</text><line class="e" x1="59" y1="77" x2="82" y2="77" marker-end="url(#ah8)"/><rect class="n" x="83" y="62" width="109" height="30" rx="3"/><line class="kd" x1="99" y1="62" x2="99" y2="92"/><text class="t" x="137.5" y="77" dy=".35em" text-anchor="middle">head: 10</text><line class="kd" x1="176" y1="62" x2="176" y2="92"/><line class="kd" x1="86" y1="89" x2="96" y2="65"/><circle class="dot" cx="184" cy="71.6" r="2.6"/><line class="e" x1="184" y1="71.6" x2="225" y2="71.6" marker-end="url(#ah8)"/><circle class="dot" cx="234" cy="82.4" r="2.6"/><line class="e" x1="234" y1="82.4" x2="193" y2="82.4" marker-end="url(#ah8)"/><rect class="n" x="226" y="62" width="62" height="30" rx="3"/><line class="kd" x1="242" y1="62" x2="242" y2="92"/><text class="t" x="257" y="77" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="272" y1="62" x2="272" y2="92"/><line class="kd" x1="275" y1="89" x2="285" y2="65"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Delete from end. Changed: 20.next = NULL (tail = 20), node 30 freed</figcaption></figure>

Search and modify.

Search(key): Step 1: p=head, pos=1. Step 2: While p: if p->data==key, return p (pos); else p=p->next, pos++. Step 3: Return NULL, "not found".
Modify(key, val): Step 1: p=Search(key). Step 2: If p is NULL, report not found; else p->data=val.

Trace on 10 <-> 20 <-> 30: key 20 is found at pos 2 after 2 comparisons, and modify to 25 gives 10 <-> 25 <-> 30. Key 40 compares 10, 20, 30, then p is NULL: "not found". Backward search starts at tail with p=p->prev: key 10 compares 30, 20, 10.

Insert at position pos (C).

#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *prev, *next; } *head=NULL;
void insertAt(int val, int pos) {
    struct Node *n, *p=head;
    if (pos<1||!(n=malloc(sizeof *n))) { printf("Error\n"); return; }
    n->data=val; n->prev=n->next=NULL;
    if (pos==1) { n->next=head; if (head) head->prev=n; head=n; return; }
    for (int i=1; p&&i<pos - 1; i++) p=p->next;
    if (!p) { printf("Invalid position\n"); free(n); return; }
    n->next=p->next; n->prev=p;
    if (p->next) p->next->prev=n;
    p->next=n;
}
void display(void) { for (struct Node *p=head; p; p=p->next) printf("%d ", p->data); }
int main(void) { insertAt(10, 1); insertAt(30, 2); insertAt(20, 2); display(); return 0; }  // 10 20 30

Answer frame. Versus singly: points 1-3, delete code. Algorithms: steps, before/after diagrams, pros, cons. Search: algorithm, both traces. Program: checks, walk to pos-1, four updates.

Pitfall: Missing NULL checks on p->next and head, or wrong pointer-update order.

Asked: [7 marks] (Nov 2022) How doubly linked list is better than a linked list? Justify with examples. Asked: [14 marks] (Dec 2023) Define doubly linked list; algorithms to insert at the beginning and delete from the end; advantages and disadvantages. Asked: [7 marks] (Jun 2023) Write a program in C to insert a node at any specified position in doubly linked list. Asked: [7 marks] (Dec 2024) What are the drawbacks of single linked list? Write and explain the algorithm for search and modify operations in doubly linked list with example.

Application of linked list: polynomial manipulation

Definition. <mark>A polynomial is stored as a linked list whose nodes hold a coefficient, an exponent and a next pointer, in decreasing order of exponent.</mark>

Key points.

Node: struct Term { int coef, exp; struct Term *next; };.
Other applications: stacks, queues, adjacency lists, and the free (available-space) list from which malloc takes blocks and to which free returns them.

Step 1: p=A, q=B, result R=NULL.
Step 2: While p and q: if exponents are equal, append the coefficient sum unless 0, advance both; else append the larger-exponent term, advance it.
Step 3: Append the remaining terms.

struct Term *R=NULL, *t;              // result and its tail
void append(int c, int e) {             // create a node, add at R's tail
    if (c==0) return;  struct Term *n=malloc(sizeof *n); n->coef=c; n->exp=e; n->next=NULL;
    if (!R) R=n; else t->next=n;
    t=n;
}
void add(struct Term *p, struct Term *q) {
    while (p&&q)
        if (p->exp==q->exp) { append(p->coef+q->coef, p->exp); p=p->next; q=q->next; }
        else if (p->exp>q->exp) { append(p->coef, p->exp); p=p->next; }
        else { append(q->coef, q->exp); q=q->next; }
    for (; p; p=p->next) append(p->coef, p->exp);
    for (; q; q=q->next) append(q->coef, q->exp);
}

Example. $A=5x^3+4x^2+2$, $B=3x^3-4x^2+6x+1$: $x^3$: $5+3=8$; $x^2$: $4-4=0$, dropped; $x$: 6 from $B$; constant $2+1=3$. $R=8x^3+6x+3$.

Asked: [7 marks] (Jun 2023) What is the application of linked list? Also write the algorithm how to add two polynomials using linked list.

Last-minute revision

O upper, Omega lower, Theta tight.
$A[99,49]$ is 44802; $B[3,3,3]$ is 1486.

Memory hooks

Big-O Over, Omega floor, Theta Together.
Array: address by arithmetic; list: by pointer.
Overflow n<mark>MAX, underflow n</mark>0.

Coverage checklist

Concepts of Data and Information: data types; data versus information.
Classification of Data structures: types; array versus linked list; classification.
Abstract Data Types: ADT with example; ADT, operations, cost.
Implementation aspects: Memory representation: 2-D array in memory.
Data structures operations and its cost estimation: notations; recurrence.
Introduction to linear data structures- Arrays: numericals; sparse; compaction.
Linked List: Representation of linked list in memory: create; insert at position.
different implementation of linked list: operations; insert after.
Circular linked list: not asked.
doubly linked list, etc: versus singly; program; search, modify.
Application of linked list: polynomial manipulation using linked list, etc: polynomial addition.

Account

Data Structures (AD-303) - Unit 1 Short Notes

How unit 1 is examined

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, etc

Application of linked list: polynomial manipulation

Last-minute revision

Memory hooks

Coverage checklist