---
title: "List and its operations"
subject: "Data Structure and Algorithm"
chapter: 3
key: "semester_4/data_structure_and_algorithm:list-and-operations"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/list-and-operations
site: BCT Engineering
---

# List and its operations

Data Structure and Algorithm · Chapter 3: List

- Asked in: 2070 Magh, 2+4 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/list-and-operations
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-3

## Question

What is list? Explain the operations that can be performed in lists.

## Short answer

A list is a finite ordered collection of same-type elements with positions, which can grow or shrink. Operations include create, empty/full test, size, traverse, insert, delete, search/retrieve, replace, sort, merge and copy; array insertion/deletion costs O(n), linked after known node is O(1).

## Answer

A **list** is a finite, ordered collection of elements of the same type, where each element has a position (first, second, ... last). Elements may be repeated and the list can grow or shrink: `L = (a₁, a₂, ..., aₙ)`; n = 0 gives the empty list. It can be implemented with an array (contiguous list) or with links (linked list).

#### Operations on a list
1. **Create / initialise** – make an empty list (n = 0).
2. **Empty / Full test** – check whether the list has no element or no free space (full applies only to array lists).
3. **Size (length)** – return the number of elements.
4. **Traverse (display)** – visit every element once from first to last.
5. **Insert** – add a new element at the beginning, end or at a given position k. Elements from position k onward move one place right (array) or a link is changed (linked list).
6. **Delete** – remove the element at a given position or with a given value. Later elements move one place left (array).
7. **Search / retrieve** – find the position of a value, or fetch the element at position k.
8. **Replace (update)** – change the value at position k.
9. **Sort / Merge / Copy** – arrange elements in order, join two lists, or duplicate a list.

#### Example (array list, n = 4)
```text
Index :  0   1   2   3   4
List  : 10  20  30  40   _
Insert 25 at position 2  -> shift 30, 40 right
List  : 10  20  25  30  40
Delete position 0        -> shift all left
List  : 20  25  30  40
```
Insertion or deletion in an array list costs O(n) because of shifting; retrieval by position is O(1). In a linked list, insertion/deletion after a known node is O(1), but reaching the k-th element is O(n).

#### Insert/delete in C
```c
#include <stdio.h>
#define MAX 10

int list[MAX];          /* contiguous storage */
int n = 0;              /* number of elements currently in the list */

int insert(int pos, int x) {          /* pos = 0..n */
    if (n == MAX || pos < 0 || pos > n) return 0;   /* overflow / bad position */
    for (int i = n - 1; i >= pos; i--) list[i + 1] = list[i];  /* shift right */
    list[pos] = x;
    n++;
    return 1;
}

int delete_at(int pos) {              /* pos = 0..n-1 */
    if (n == 0 || pos < 0 || pos >= n) return 0;    /* underflow / bad position */
    for (int i = pos; i < n - 1; i++) list[i] = list[i + 1];   /* shift left */
    n--;
    return 1;
}

void traverse(void) {
    for (int i = 0; i < n; i++) printf("%d ", list[i]);
    printf("\n");
}

int main(void) {
    insert(0, 10); insert(1, 30); insert(1, 20);   /* 10 20 30 */
    traverse();
    delete_at(0);                                    /* 20 30 */
    traverse();
    return 0;
}
```

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which describes a list?
   A. Unordered set with no repeats
   B. Finite ordered collection where each element has a position
   C. LIFO-only structure
   D. Two-dimensional table
   Answer: B. A list is ordered and elements may repeat. (Key point: List definition)

2. For which implementation is the Full test meaningful?
   A. Linked list
   B. Array list
   C. Both equally
   D. Neither
   Answer: B. Only arrays have a fixed capacity. (Key point: Full test)

3. Inserting at position k in an array list requires:
   A. Shifting elements from k onward right
   B. Shifting elements before k left
   C. Nothing
   D. Freeing a node
   Answer: A. Room is made by moving later elements right. (Key point: Insert in array)

4. Which costs are correct for an array list?
   A. Retrieve O(n), insert O(1)
   B. Retrieve O(1), insert/delete O(n)
   C. All O(1)
   D. All O(n)
   Answer: B. Direct indexing is O(1) but shifting makes insert/delete O(n). (Key point: Complexities)

## Related in Data Structure and Algorithm

- [Linked list and its basic operations](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Alinked-list-and-operations) — Data Structure and Algorithm, chapter 4
- [Linear and circular queue operations](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Alinear-circular-queue-algorithms) — Data Structure and Algorithm, chapter 2
- [Stack definition and basic operations](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-operations-algorithms) — Data Structure and Algorithm, chapter 2

## Related in other subjects

- [Lathe operations, taper turning and turning calculations](https://www.bctengineer.com/question.md?key=semester_4%2Fmanufacturing_and_production_processes%3Alathe-operations-taper-turning-numerical) — Manufacturing and Production Processes, chapter 7