Linked List
- A Linked List is a data structure composed of nodes: containers that each hold a single element. These nodes are "linked" to one another via pointers.
- Singly Linked List v.s. Doubly Linked List
- Question: Notice that when we look for an element in the middle of the Linked List, we start at the head and step forward. This works fine if the index is towards the beginning of the list, but what about when the index of interest is large (i.e., closer to n)? Can we speed things up?
Ans: If the linked list nodes are sorted, by using doubly linked list, we can decide to start from head or tail.
Operations
insert
find
remove
Worst case: O(n)
Question: Notice that the node we removed still exists in this diagram. Not considering memory management (i.e., only thinking in terms of data structure functionality), is this an issue?
Ans: