Skip to main content

ADT of linked list

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.

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

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.

/* 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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 1 questions →