An ADT is a contract: the operations and what they mean. A data structure is one way to implement that contract. A stack is an ADT. A Python list used only at the end is one implementation.

Goal

Define a tiny Stack ADT two ways — list and linked nodes — and print the same pops.

The contract

Stack:

push(x) — add x
pop() — remove and return the last pushed
empty() — True when there is nothing to pop

Last in, first out. The contract does not say “use a list”.

List implementation

class ListStack:
    def __init__(self):
        self._data = []

    def push(self, x):
        self._data.append(x)

    def pop(self):
        return self._data.pop()

    def empty(self):
        return not self._data

s = ListStack()
for city in ["Nairobi", "Mombasa", "Kisumu"]:
    s.push(city)
print(s.pop(), s.pop(), s.empty())

Linked implementation

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

class LinkedStack:
    def __init__(self):
        self._head = None

    def push(self, x):
        self._head = Node(x, self._head)

    def pop(self):
        value = self._head.value
        self._head = self._head.next
        return value

    def empty(self):
        return self._head is None

s = LinkedStack()
for city in ["Nairobi", "Mombasa", "Kisumu"]:
    s.push(city)
print(s.pop(), s.pop(), s.empty())

Same ADT, two structures. Analysis (next chapters) asks how much each operation costs.

Tip

Write the operations first. Pick the structure from the costs you need — not the other way around.