## Linked List Overview

1 | class Node { |

## 3.2 Singly Linked List (pros and cons)

- Arrays are not adaptable and cannot change in size.
- Vectors skirt this problem by allowing expansion and reduction.
- However, both arrays and vectors are inefficient if used to insert and remove data because they need to be shifted left and right to keep data sorted or fill the gap when data is removed.
- Therefore,
**linked list**is a collecting of nodes that form a linear ordering.- A linked list contains: a)
**internal****data**, and b) a**pointer**.- First node is called the
**head**and last node is called the**tail**.**- Linked lists can be maintained in an order and do not have a predetermined size**

- First node is called the

- A linked list contains: a)

- Therefore,

- However, both arrays and vectors are inefficient if used to insert and remove data because they need to be shifted left and right to keep data sorted or fill the gap when data is removed.

- Vectors skirt this problem by allowing expansion and reduction.

## 3.2.1 Implementing a Singly Linked List

1 | class StringNode { //a node |

1 | //Constructor creates an empty list by setting head pointer to NULL |

1 | //checks if list is empty |

## 3.2.2 Insertion to the Front of a Singly Linked List

- Create a new node
- Set new node pointer to point to current head
- Set head to point to the new node.

1 | void StringLinkedList::addFront(const string& e) { |

## 3.2.3 Removal from the Front of a Singly Linked List

Assume that the user has checked that the list is nonempty before applying this operation. (A more careful implementation would throw an exception if the list were empty.) The function deletes the node in order to avoid any memory leaks.

1 | void StringLinkedList::removeFront() { |

## Inserting at the end of a singly linked list

Since we did not keep a pointer to the tail

We will have a hard time inserting in the end

Step 1: Navigate the list to reach the last node

1 | //nagivate to the last node, I guess v is the first node |

## Inserting in the middle of a singly linked list

Assuming that we have the pointer to node v,

- Insert a node between
`v`

and`w`

,- where
`w`

is a node immediately after v (which means`v->next = w`

)

- where

1 | Node* inBetween = new Node(); |

## Removing a node from the end of a singly linked list

- Since we did not keep a pointer to the
`tail`

in a singly linked list, we we will have to traverse the entire list.

1 | //Navigate the list to the last node, but be careful to save the pointer to the second last node. |

## Removing in the middle (not the beginning or end) in singly linked list

- Assume we have the pointer to node v.

•We want to delete a node that is between v and w.**(v, middle, w)**

Basically, save the pointer of the middle node, connect v and w together by using the middle node, and then deleting the middle node finally after its served its purpose–as a pointer to w.

(Notice how we don’t even have the actual name of node between v and w–we can just access it using `v-next`

)

1 | //Copy the middle node to delete. |

## Implementing a Generic Singly Linked List (IMPORTANT)

#### Contrast this to typedef (Page 130)

In Section 3.2.1 assumes that the element type is a character string. It is easy to convert the implementation so that it works for an arbitrary element type through the use of C++’s template mechanism. The resulting generic singly linked list class is called SLinkedList.

**The element type associated with each node is parameterized by the type variable E.** In contrast to our earlier version in Code Fragment 3.13, references to the data type “string” have been replaced by “E.” When referring to our templated node and list class, we need to include the suffix “.”” For example, the class is SLinkedList and the associated node is SNode.

1 | template <typeName E> |

In Code Fragment 3.20, we present the class member functions. Note the similarity with Code Fragments 3.15 through 3.17. Observe that each definition is prefaced by the template specifier template .

1 | template <typename E> |

1 | template <typename E> |

1 | template <typename E> |

1 | template <typename E> |

1 | void SLinkedList<E>::addFront(const E& e) { |

1 | void SLinkedList<E>::removeFront() { |

### Using the generic singly linked list

1 | SLinkedList<string> a; //list of strings |