---
title: "ADT of linked list"
subject: "Data Structure and Algorithm"
chapter: 1
key: "semester_4/data_structure_and_algorithm:adt-linked-list-definition"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/adt-linked-list-definition
site: BCT Engineering
---

# ADT of linked list

Data Structure and Algorithm · Chapter 1: Concept of data structure

- Asked in: 2075 Baisakh, 2+4 marks
- Video: [Data Structures: List as abstract data type](https://www.youtube.com/watch?v=HdFG8L1sajw) — mycodeschool
- 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/adt-linked-list-definition
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-1

## Question

Define ADT and construct ADT of Linked List using value definition and operator definition.

## Short answer

An ADT is defined by value and operator definitions, hiding implementation. The linked list ADT has a value definition: a sequence of nodes each with info and a next pointer, headed by a head pointer; operator definitions include getnode, freenode, insafter, delafter, insbeg, delbeg, traverse, and search, with pre- and postconditions specifying behavior without implementation details.

## Answer

An **abstract data type (ADT)** is a mathematical model of a data type that is defined by its **values** and the **operations** allowed on them, without saying how they are stored or coded. The user sees only *what* the type does; *how* it is done (array, linked list, etc.) stays hidden. In Tenenbaum's style an ADT has two parts: a **value definition** and an **operator definition**.

#### ADT of a linked list

A linked list is a linear collection of nodes; each node holds `info` and a pointer `next` to its successor.

```text
/* Value definition */
abstract typedef <<info, next>> LIST(NODE);   /* sequence of nodes; every node
                                                 holds info and the address of the
                                                 next node; last next = NULL */
condition  list has a header pointer 'head' (NULL when list is empty);

/* Operator definition */
abstract NODE getnode()
   postcondition getnode is a new node with undefined info and next;

abstract freenode(p)   NODE p;
   postcondition node p is returned to free storage;

abstract insafter(p, x)   NODE p; eltype x;
   precondition  p != NULL;
   postcondition new node with info x placed after p;
                 next(new) == next(p)before;  next(p) == new;

abstract eltype delafter(p)   NODE p;
   precondition  p != NULL and next(p) != NULL;
   postcondition delafter == info(next(p)before);
                 next(p) == next(next(p)before);

abstract insbeg(head, x);   postcondition a new node holding x is the first node;
abstract delbeg(head);      precondition head != NULL;
                            postcondition first node removed; head == next(head)before;
abstract traverse(head);    postcondition every info visited once, in order;
abstract search(head, x);   postcondition returns node holding x or NULL;
```

A concrete implementation may use dynamic memory (`malloc`) or an array of nodes with `avail` list; the ADT remains the same.

## Check yourself

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

1. In the linked list ADT, every node holds:
   A. Only info
   B. info and a pointer next to its successor
   C. Only a pointer to the previous node
   D. An index and a size
   Answer: B. Each node has info and next; the last next is NULL. (Key point: Node contents)

2. How is an empty list represented?
   A. head points to the last node
   B. next of head is 1
   C. head is undefined
   D. head is NULL
   Answer: D. The header pointer head is NULL when the list is empty. (Key point: Empty list)

3. After insafter(p, x), which is true?
   A. next(p) == old next(p)
   B. new is placed before p
   C. next(new) == NULL always
   D. next(new) == old next(p) and next(p) == new
   Answer: D. The new node takes p's old successor and p now points to the new node. (Key point: insafter postcondition)

4. What is the precondition of delafter(p)?
   A. p == NULL
   B. head == NULL
   C. p != NULL and next(p) != NULL
   D. next(p) == NULL
   Answer: C. There must be a node after p to delete. (Key point: delafter precondition)

## Related in Data Structure and Algorithm

- [ADT of stack: value and operator definition](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aadt-stack-value-operator) — Data Structure and Algorithm, chapter 1
- [Data type and ADT definition](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adata-type-and-adt) — Data Structure and Algorithm, chapter 1, asked 3×

## Related in other subjects

- [Operator overloading: need and definition](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Aoperator-overloading-why-define) — Object Oriented Programming, chapter 5, asked 3×