Past exam question: 2075 Baisakh (Back), Q1(b)
Open in the Padhaiko appQuestion
and construct ADT of Linked List using value definition and operator definition.
Solution
Value Definition of Linked List ADT:
- A Linked List is a finite ordered sequence of nodes of homogeneous element type
Element, accessed via aheadreference, where each node pairs a data value with a link to its successor (and the last node links toNULL). - When , is the empty list (
head == NULL).
Operator Definition of Linked List ADT:
createList()List: returns an empty list (head = NULL).isEmpty(L)boolean: returnstrueiffLcontains zero nodes.insertFirst(L, x)/insertAt(L, pos, x)List: preconditions: validpos(); inserts a node with valuexatpos.deleteFirst(L)/deleteAt(L, pos)Element: precondition:!isEmpty(L)and validpos; removes and returns the element atpos.search(L, x)position/Node*: returns the first node matchingx, orNULLif absent.traverse(L)void: visits every node sequentially fromheadtoNULL.
Answer:
The Linked List ADT consists of a value definition (an ordered dynamic sequence of nodes accessed from head) and an operator definition (createList, isEmpty, insertFirst/insertAt, deleteFirst/deleteAt, search, and traverse).