Reading Assignment: All of Programming Chapter 21 Linked Lists

Linked list is a data structure which is a linear sequence of nodes connected by pointers.

1 | template<typename T> |

There are a few interesting things to note about this class declaration.

First, the inner class Node has a field which is a pointer to a node-the type is recursively defined: a Node has a pointer to a Node. As with recursive algorithms, recursive data-types are fine as long as they are well-founded. For types in C and C++, the compiler requires that until a type is fully declared, only pointers to that type may be used. This requirement ensures that all recursively defined types are well-founded and take finite space.

There are some common variations on the basic linked list structure. The variation we saw is a *singly linked list*, meaning that each node points only at the next element. An alternative is a *doubly linked list*, in which each node points not only at the next element, but also at the previous element. The advantage of a doubly linked list is that it makes traversing the list in the reverse direction much easier.

ADT for doubly linked list:

1 | template<typename T> |

It is also possible to make a *circular list*, in which there is no last node, but instead, the nodes form a circle.

## Linked List Basic Operations

### Add to Front

If we want to add an element to linked list, adding to the front is the easiest place to do so.

Two examples are given by video: One is singly linked list, another is doubly linked list.

Singly Linked list version:

1 | void addFront(int data){ |

Doubly Linked list version:

1 | void addFront (int data) { |

### Add to Back

If our list has a `tail`

pointer, we can just use the `tail`

pointer to find the last node. Otherwise, we must iterate through the nodes in the list, looking for one whose next field is `NULL`

.

1 | void addBack(int data){ |

### Searching

time complexity: O(n)

### Copying

If we want to make a deep copy of a linked list, we need to iterate through its nodes, creating new nodes with the same data, and linking them together so that the items appear in the same order. One way to do this would be to iterate through our source list in reverse order, and add each item to the front of the destination list.

### Destruction

We need to use a temporary variable to remember the next node in the list, delete the current node, then go to the next node.

1 | ~LinkedList() { |

## Insert in Sorted Order

### Pointer to Node Before

One common approach to inserting in a particular position in a linked list is to search through the list for the node before where we want to add. That is, we have a `Node * current`

and iterate through our list looking for the situation where we want to set `current`

‘s `next`

to the node we want to add.

Such an approach has a corner case when we want to add to the front of the list.

1 | void addSorted(const T & data) { |

### Recursion

As linked list have recursive structure(Nodes have pointers to Nodes), they lend themselves quite naturally to recursive algorithm. Such algorithms typically take a `Node *`

as a parameter, and have a recursive case on `current->next`

. For operations which modify the structure of the list, these algorithms typically return a `Node *`

which points at the resulting sequence of nodes, the method then update `current`

based on this.

1 | template<typename T> |

### Pointer-to-a-pointer

We can have a much more elegant iterative approach by recognizing the similarity between the two-they are both `Node * s`

-and finding a way to deal with them uniformly. In particular, we can have a `Node **`

which points at `the box we might want to change`

-and then we can point it at either `head`

or the `next`

field of any node.

1 | void addSorted(int dataToAdd) { |

## Removing from a List

### Remove from Front/Back

Removing from the head of a linked list can always be done in $O(1)$ time. After checking that the list is not empty, we just need to store the current value of the head pointer in a temporary variable, update the `head`

pointer to `head->next`

, then `delete`

the original head node.

If our list is doubly linked, we need to update the `prev`

pointer of new head node if the list is not empty. Likewise, if our list has a tail pointer, we need to check to see if it now empty, and if so, update the tail pointer to `NULL`

.

### Other Removals: Pointer to Node Before

As with inserting in the middle of the list, we can remove from the middle of the list by finding the node *before* the one we want to remove.

Once we have a pointer to the node before the one we want to remove, we first need to store the pointer to the node we want to delete, that is `current->next`

in a temporary variable, so we can delete it later. We then need to update `current-next`

to be `current->next->next`

, which removes the desired node from the list.

### Other Removals: Recursion

Here, we have two base cases:

- If the current node is
`NULL`

, the list does not contain the item we are trying to delete, so we can just return the list unchanged, that is return`NULL`

. - If the current node meets our criteria for deletion, we can remove the item from the list by returning everything after it, although we need to first delete the node we are removing.

1 | template<typename T> |

### Other Removals: Pointer-to-a-pointer

As with inserting, this gives us an elegant iterative approach because we no longer have a corner case for removing the head. We can keep a `Node **`

which starts at `&head`

and represents the box we might want to change, then iterate along our list, trying to find the proper place from which to remove. Once we find it, we perform the appropriate pointer manipulations.

### Remove All Occurrences

1 | template<typename T> |

Here, we have templated our private remove helper method over whether or not it should remove all elements(true) or just one(false). Recall that we can template over values as well as over types. Now, we have one copy of the code to do the work for removal, with a single if statement that choose whether to recurse or not. Our public methods then simply instantiate the remove template with either false or true as appropriate, and call it.

## Iterators

Iterators are objects which encapsulate a position in a data structure, and give us a way to access and move through the elements without knowing the internal of that structure.

### Implementation

We can implement the iterator by writing an inner class inside of our LinkedList class. As an inner class of linked list, the iterator is a part of the LinkedList class, and therefore it is fine for it to know about the implementation details of the list.

1 | template<typename T> |

## Uses for ADTs

### Stacks

We can both add to and remove from the front in $O(1)$ time, which is the best $O$ we can hope for. One downside of a linked list implementation is that we have a bit of space overhear(for every element, we store the element, as well as a next pointer).

### Queues

We can implement both of insertion and removal in $O(1)$ time.

### Sets

If we want a Set that is efficient for large $N$, we can use either a binary search tree or a hash table.