An abstract data type (ADT) specifies a collection of data and the operations available on it, without specifying how those operations are implemented. It tells a programmer what they can do with the data—not how it is represented in memory.

Separating behaviour from implementation

An ADT describes the values it can hold and which operations are permitted, including what each operation does. A set, for example, holds distinct elements. It supports adding an element, removing an element and checking membership. Adding an element that's already present does not create a duplicate.

A data structure is a concrete arrangement of data in memory that supports particular operations. The same ADT can be implemented using different data structures, each with different memory requirements and performance.

Why abstraction is useful

Using an ADT lets a programmer concentrate on the problem being solved. They need to know what an operation does, but not every step used to perform it.

An implementation can be replaced without changing the calling code, as long as the available operations and their behaviour stay the same. Replacing a linked-list implementation of a set with a hash-table implementation, for example, could improve typical membership-check performance. The meaning of membership would not change.

Implementation choices still matter. Two implementations may produce identical results yet differ substantially in speed and memory use. Which one is appropriate depends on the operations a program performs most often.

Key terms: abstract data type (ADT), data structures, associated operations, high-level description.

When evaluating a linked list, weigh its flexible size and link-based updates against the extra memory it needs and its sequential access. The best choice depends on the operations required—and on whether the relevant node is already known.

Singly, doubly and circular lists

A linked list stores a sequence of elements in nodes connected by references. Those nodes need not sit next to each other in memory.

Each node holds a data item and one or more references to other nodes. The head identifies the first node; a tail, if maintained, identifies the last.

Insertion and deletion change links

To insert 20 between 12 and 28 in a singly linked list, first point the new node's next reference to 28. Then point 12's next reference to 20. The order matters: it preserves access to the rest of the list.

Inserting between two nodes in a doubly linked list also requires connecting the new node's previous reference and updating the following node's previous reference. Deletion reconnects both neighbours. The predecessor's next reference bypasses the removed node, while the successor's previous reference bypasses it in the other direction.

For a circular list, inserting or deleting at the head or tail must preserve the final link back to the head. Deleting the only node leaves an empty list, not a node that still points to itself.

Traversal and search

Traversal visits the nodes of a data structure in a systematic order. In a singly linked list, begin at the head and keep following next until you reach null.

Search checks nodes to find a requested value. Searching for 40 in 12 → 28 → 40 examines 12, then 28, then 40. If the value is absent, the search must examine the whole list.

Reaching null is not a valid stopping rule for a circular list. After processing the starting node, stop when the next step would revisit it. With a doubly linked list, you can also traverse from tail to head by following previous references.

Linked lists compared with arrays

A linked list is useful when a sequence changes frequently and updates happen at already-known nodes. Singly linked lists use relatively few references. A doubly linked list is preferable when you need to move backwards or delete a known node.

For repeated cycling through elements, such as rotating through a set of active tasks, a circular list is a suitable choice. Its stopping conditions and head/tail updates are easier to get wrong, though.

An array is usually preferable when indexed access dominates or compact storage matters. Don't assume linked-list insertion is always faster: finding the insertion point can take longer than the insertion itself.

Key terms: singly, doubly, circular, insertion, deletion, traversal, search, memory utilization, performance.

Construct a linked list by creating nodes and connecting their references. Apply insertion, deletion, traversal and search by changing or following those references, while preserving the rules of the chosen list type.

A shared worked example

Each implementation below begins with 12 → 28 → 40, inserts 20 after 12, deletes 28, then traverses the remaining nodes while searching for 40. The final sequence is 12 → 20 → 40.

The examples deliberately keep references to the relevant nodes. Therefore, the insertion and deletion require only link changes; finding those nodes in a larger list would be a separate search.

Singly linked list

Java

1  public class SinglyExample {
2      static class Node {
3          int data;
4          Node next;
5          Node(int data) { this.data = data; }
6      }
7      public static void main(String[] args) {
8          Node head = new Node(12);
9          Node middle = new Node(28);
10         Node tail = new Node(40);
11         head.next = middle;
12         middle.next = tail;
13         Node added = new Node(20);
14         added.next = head.next;
15         head.next = added;
16         added.next = middle.next;
17         int found = -1;
18         Node current = head;
19         while (current != null) {
20             if (current.data == 40) {
21                 found = current.data;
22             }
23             System.out.println(current.data);
24             current = current.next;
25         }
26         System.out.println(found);
27     }
28 }

Python

1  class Node:
2      def __init__(self, data):
3          self.data = data
4          self.next = None
5  head = Node(12)
6  middle = Node(28)
7  tail = Node(40)
8  head.next = middle
9  middle.next = tail
10 added = Node(20)
11 added.next = head.next
12 head.next = added
13 added.next = middle.next
14 found = -1
15 current = head
16 while current is not None:
17     if current.data == 40:
18         found = current.data
19     print(current.data)
20     current = current.next
21 print(found)

In Java, lines 14–15 insert the new node and line 16 bypasses 28. Python performs the same changes on lines 11–13. Neither program searches by array index: both follow node references.

Doubly linked list

Java

1  public class DoublyExample {
2      static class Node {
3          int data;
4          Node next, previous;
5          Node(int data) { this.data = data; }
6      }
7      public static void main(String[] args) {
8          Node head = new Node(12);
9          Node middle = new Node(28);
10         Node tail = new Node(40);
11         head.next = middle; middle.previous = head;
12         middle.next = tail; tail.previous = middle;
13         Node added = new Node(20);
14         added.previous = head;
15         added.next = middle;
16         middle.previous = added;
17         head.next = added;
18         added.next = middle.next;
19         middle.next.previous = added;
20         int found = -1;
21         Node current = head;
22         while (current != null) {
23             if (current.data == 40) { found = current.data; }
24             System.out.println(current.data);
25             current = current.next;
26         }
27         System.out.println(found);
28     }
29 }

Python

1  class Node:
2      def __init__(self, data):
3          self.data = data
4          self.next = None
5          self.previous = None
6  head = Node(12)
7  middle = Node(28)
8  tail = Node(40)
9  head.next = middle
10 middle.previous = head
11 middle.next = tail
12 tail.previous = middle
13 added = Node(20)
14 added.previous = head
15 added.next = middle
16 middle.previous = added
17 head.next = added
18 added.next = middle.next
19 middle.next.previous = added
20 found = -1
21 current = head
22 while current is not None:
23     if current.data == 40:
24         found = current.data
25     print(current.data)
26     current = current.next
27 print(found)

After deletion, 20's next reference points to 40, and 40's previous reference points to 20. A backward traversal would start at the tail and follow previous references, visiting 40, 20, 12.

Circular linked list

Java

1  public class CircularExample {
2      static class Node {
3          int data;
4          Node next;
5          Node(int data) { this.data = data; }
6      }
7      public static void main(String[] args) {
8          Node head = new Node(12);
9          Node middle = new Node(28);
10         Node tail = new Node(40);
11         head.next = middle;
12         middle.next = tail;
13         tail.next = head;
14         Node added = new Node(20);
15         added.next = head.next;
16         head.next = added;
17         added.next = middle.next;
18         int found = -1;
19         Node current = head;
20         if (head != null) {
21             do {
22                 if (current.data == 40) { found = current.data; }
23                 System.out.println(current.data);
24                 current = current.next;
25             } while (current != head);
26         }
27         System.out.println(found);
28     }
29 }

Python

1  class Node:
2      def __init__(self, data):
3          self.data = data
4          self.next = None
5  head = Node(12)
6  middle = Node(28)
7  tail = Node(40)
8  head.next = middle
9  middle.next = tail
10 tail.next = head
11 added = Node(20)
12 added.next = head.next
13 head.next = added
14 added.next = middle.next
15 found = -1
16 current = head
17 if head is not None:
18     while True:
19         if current.data == 40:
20             found = current.data
21         print(current.data)
22         current = current.next
23         if current is head:
24             break
25 print(found)

Trace of the worked run

The data updates are identical in all three versions. The difference is the link that terminates traversal.

This traversal-and-search trace applies to each Java and Python pair. A value shown for current identifies the data in the node it references.

The final output line is the search result. Here the search shares the traversal loop, so it continues visiting nodes even after a match. A separate membership search could stop immediately when it found the requested value.

Boundary cases

The worked programs update interior nodes. A general implementation must also handle these cases:

• Empty list: traversal and search visit no nodes. Insertion creates the first node and establishes the head and, if used, tail.
• Insertion at the head: link the new node to the old head, then replace the head reference. In a doubly linked list, also update the old head's previous reference.
• Deletion at the head: replace head with its successor. In a doubly linked list, the new head's previous reference becomes null.
• Update at the tail: maintain the tail reference. In a doubly linked list, its next reference is null.
• Circular boundary update: ensure tail.next still identifies head. A one-node circular list points to itself; deleting that node sets both head and tail to null.
• Unsuccessful search: stop at null in a non-circular list or after one complete circuit in a circular list.

Removing a node from the list means disconnecting it from the reachable sequence. In these examples, the variable middle still refers to the removed node; removal does not itself erase that object.

Key terms: singly, doubly, circular, insertion, deletion, traversal, search.

To explain a BST, link its ordering rule to search, insertion, deletion and traversal. That rule lets a search discard an entire subtree.

A binary search tree (BST) is a binary tree where every key in a node's left subtree is smaller than that node's key, and every key in its right subtree is larger. The examples here use unique keys.

Structure and organization

Each node holds a key and references to at most two children. At the top is the root. A leaf has no children, while a subtree contains a node and all the nodes below it.

The ordering rule covers whole subtrees, not just immediate children. Take 24: it is greater than its parent 18, but it must still be smaller than the root 30 because it lies in 30's left subtree.

Searching and inserting

To search for 24:

1. Compare with 30. Since 24 is smaller, follow the left reference.
2. Compare with 18. Since 24 is larger, follow the right reference.
3. Compare with 24. The key has been found.

If the required reference is null before a match is found, the key is absent. There's no need to inspect the other subtree: none of its keys can match.

Deleting nodes

Deletion must leave the ordering rule intact. The method depends on which of three cases applies:

To find the inorder successor in the two-child case, move right once, then left as far as possible. The successor has no left child. Removing it from its old position therefore becomes a zero-child or one-child case.

Traversal orders

Every traversal visits each node once. What changes is when it processes a node relative to its subtrees. The results below use the original tree, before inserting 22 or performing deletions.

Inorder traversal produces keys in ascending order: it processes all smaller keys before the node and all larger keys afterwards.

Shape affects performance

Search, insertion and deletion follow paths through the tree. Their performance therefore depends on its height. In a reasonably balanced tree, these operations take O(log n) time. A badly skewed tree can require O(n).

Insert 10, 18, 24, 30 in that order, for example, and the result is a chain of right children rather than a branching tree. A BST doesn't automatically keep itself balanced. Traversal still takes O(n), because it must visit every node.

Key terms: binary search tree (BST), data organization, insert, delete, traverse, search.

Construct sets from collections of values, then apply membership checks, updates and set operations. Judge the result by which elements it contains, not by the order in which they appear.

A set is an unordered collection of unique elements. Adding an element already present leaves the membership unchanged.

Uniqueness and lack of positional order

Constructing a set from 2, 4, 4, 6 produces {2, 4, 6}. The repeated 4 is stored only once. A set has no first, second or third element as part of its abstract behaviour, so indexed access is not a set operation.

An implementation may display elements in some order, but that order should not be treated as the meaning of the set.

Union, intersection and difference

Union and intersection give the same result if the operands are exchanged. Difference generally does not: A minus B and B minus A answer different questions.

Membership, subsets and supersets

A subset has every one of its elements contained in another set. A superset contains every element of another set.

For C = {4, 6}, C is a subset of A, and A is a superset of C. Equality is allowed: every set is both a subset and a superset of itself.

Worked implementation

These programs check whether 4 belongs to A, add 10, and remove 2. They then check whether the updated A contains all of C, followed by the reverse check. Thus they demonstrate both superset and subset checks.

They also calculate union, intersection and difference using independent sets named left and right. Printing result sizes avoids relying on an arbitrary set display order.

Java

1  import java.util.HashSet;
2  import java.util.Set;
3  public class SetExample {
4      public static void main(String[] args) {
5          Set<Integer> a = new HashSet<>(Set.of(2, 4, 6));
6          Set<Integer> c = new HashSet<>(Set.of(4, 6));
7          System.out.println(a.contains(4) ? 1 : 0);
8          a.add(10);
9          a.remove(2);
10         System.out.println(a.containsAll(c) ? 1 : 0);
11         System.out.println(c.containsAll(a) ? 1 : 0);
12         Set<Integer> left = new HashSet<>(Set.of(2, 4, 6));
13         Set<Integer> right = new HashSet<>(Set.of(4, 6, 8));
14         Set<Integer> union = new HashSet<>(left);
15         union.addAll(right);
16         Set<Integer> intersection = new HashSet<>(left);
17         intersection.retainAll(right);
18         Set<Integer> difference = new HashSet<>(left);
19         difference.removeAll(right);
20         System.out.println(union.size());
21         System.out.println(intersection.size());
22         System.out.println(difference.size());
23     }
24 }

Python

1  a = {2, 4, 6}
2  c = {4, 6}
3  print(1 if 4 in a else 0)
4  a.add(10)
5  a.discard(2)
6  print(1 if a.issuperset(c) else 0)
7  print(1 if a.issubset(c) else 0)
8  left = {2, 4, 6}
9  right = {4, 6, 8}
10 union = left | right
11 intersection = left & right
12 difference = left - right
13 print(len(union))
14 print(len(intersection))
15 print(len(difference))

In Java, testing whether A contains all of C establishes that A is a superset of C; testing whether C contains all of A establishes that A is a subset of C. Python provides methods named directly for these relationships.

Java's set-combination methods modify the receiving set, so the program copies left before each operation. The Python operators shown create new sets. Python's discard method does nothing if the element is absent; its remove method instead raises an error for an absent element. An empty Python set is created with set(), not with empty braces, which create a dictionary.

Trace of the worked run

Both programs print 1 for a true condition and 0 for a false condition.

Sets are appropriate when membership and uniqueness matter, such as collecting distinct identifiers. They are unsuitable when repeated occurrences or a meaningful sequence must be preserved.

Key terms: set, unordered, uniqueness, union, intersection, difference, subset, superset.

Explain an ADT at two levels: its public behaviour and the mechanics of a possible implementation. A set promises unique elements and membership operations; a hash table is one way to deliver those operations efficiently.

Hash tables and hash functions

A hash table stores entries in an array of locations selected using a key's hash. A hash function transforms a key into a value used to determine its storage location.

For non-integer keys, such as strings, a hash function first derives a numerical hash from the key. The result is converted into a valid table index. The function must give a consistent result for the same unchanged key; a useful function also spreads keys across the available locations.

A collision occurs when different keys are assigned the same table location. A collision does not mean that the keys are equal, so the implementation must still compare keys when locating an entry.

Resolving collisions

A lookup repeats the same hashing and collision-resolution process used for insertion. In chaining, it searches the selected chain. In linear probing, it follows the probe sequence until it finds the key or establishes that the key is absent.

Deletion in a probing table must not accidentally break a search path. A removed location can be marked as deleted so that later searches continue past it rather than treating it as a location that has never been occupied.

Load factor and performance

The load factor is the number of stored entries divided by the number of table locations. It measures how full the table is relative to its capacity.

With 3 entries and capacity 5, the load factor is 3 / 5 = 0.6. A higher load factor generally causes more collisions and more work during lookup and updates. Chaining can have a load factor greater than 1 because several entries can share a location; an open-addressed table needs available array locations for further insertions.

An implementation can allocate a larger table and rehash its existing entries. Entries must be placed again because the new capacity can change their indices; simply copying them into the same positions is not generally sufficient.

With a suitable hash function and controlled load factor, lookup, insertion and deletion typically take O(1) time. Severe collisions can make an operation O(n). Resizing also takes time because existing entries must be redistributed.

How hashing supports sets

A hash-based set stores elements as keys without separate associated values. Adding an element involves hashing it, checking the relevant location or probe sequence for an equal element, and inserting only if no equal element is already present.

Membership performs the same lookup. Removal locates the equal element and deletes its entry using the implementation's collision-handling rules. Uniqueness is therefore maintained by equality checks, not by assuming that every hash value identifies only one element.

The set ADT remains unordered even though the implementation stores elements at particular array locations. These internal positions do not give the set a meaningful positional sequence.

Java and Python collections

A map associates each unique key with a value. Unlike a set, it stores a value to retrieve using the key; assigning a new value to an existing key replaces the old association.

Java's HashMap and HashSet and Python's dict and set are hash-based collections. They hide hashing, collision resolution and resizing from the calling program. Their internal collision strategies need not be identical.

Python dictionaries preserve insertion order, but that does not make them sorted by key. Do not assume sorted iteration from HashMap, HashSet or set either.

Worked mapping and set example

The programs associate key 12 with Iris and key 17 with Moss. Updating key 12 to Fern changes its value without adding another key. Adding 12 twice to the set also leaves just one copy.

Java

1  import java.util.HashMap;
2  import java.util.HashSet;
3  public class HashExample {
4      public static void main(String[] args) {
5          HashMap<Integer, String> names = new HashMap<>();
6          names.put(12, "Iris");
7          names.put(17, "Moss");
8          names.put(12, "Fern");
9          HashSet<Integer> identifiers = new HashSet<>();
10         identifiers.add(12);
11         identifiers.add(17);
12         identifiers.add(12);
13         System.out.println(names.get(12));
14         System.out.println(names.containsKey(23) ? 1 : 0);
15         System.out.println(names.size());
16         System.out.println(identifiers.size());
17     }
18 }

Python

1  names = {}
2  names[12] = "Iris"
3  names[17] = "Moss"
4  names[12] = "Fern"
5  identifiers = set()
6  identifiers.add(12)
7  identifiers.add(17)
8  identifiers.add(12)
9  print(names[12])
10 print(1 if 23 in names else 0)
11 print(len(names))
12 print(len(identifiers))

Trace of the worked run

Choose a hash-based set when fast membership checks and uniqueness are the main requirements. Choose a map when each key must lead to an associated value. A BST is more appropriate when maintaining searchable key order and obtaining an ordered traversal are important; linked lists suit sequential link-based updates rather than fast arbitrary lookup.

Key terms: ADTs, high-level description, hash tables, hashing functions, collision resolution strategies, load factors, sets, HashMap, HashSet, dict, set.