Linked List¶
Motivation¶
Sometimes the size of the list is not known in advance.
Insertion in the middle of an array is expensive.
Linked structures store items linearly and allow quick inserts. Searching for an element becomes, more expensive.
Definition¶
- A linked list consists of nodes each of which contains data and one pointer to the next node.
- Self-referential (naturally recursive)
- tail: null, dummy, head
Operations¶
- insert(value, next=None)
- remove(node)
- search(value)
- display()
- pop()