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.
Definition¶
- A linked list consists of nodes each of which contains data, one pointer to the next node and one pointer to the previous node.
- Self-referential (naturally recursive)
- tail: null, dummy, head
Operations¶
- add(value, next=head, previous)
- remove(node)
- search(value)
- display()
- pop()