(Ch. 17) Understanding Linked Lists and Their Operations

linked list

A linked list is a series of connected nodes where each node contains data and a pointer to the next node.

linked list node parts

A data member and a pointer to the next node.

list head

A pointer that points to the first node in the list.

end of a linked list

By having the last node's pointer point to nullptr.

self-referential data structure

A structure that includes a pointer to another structure of the same type.

advantages of linked lists

Linked lists can grow/shrink dynamically and insert/delete elements more efficiently.

basic linked list operations

Appending, inserting, deleting, traversing, and destroying nodes.

appendNode function

It allocates a new node, stores the value, and attaches it at the end of the list.

traversing a linked list

Visiting each node from the head to the end of the list using their pointers.

displayList() function

To traverse the list and output each node's data.

inserting into a sorted linked list

By finding the correct position and updating the pointers accordingly.

previousNode pointer in insertNode

It keeps track of the node before the insertion point.

deleteNode function

It bypasses the node using pointers and then deletes it from memory.

destructor in a linked list class

It deallocates memory by deleting all nodes to prevent memory leaks.

doubly linked list

A list where each node has pointers to both the previous and next nodes.

circular linked list

A list where the last node points back to the first node.

STL container for doubly linked list

The list container in the Standard Template Library (STL).

STL list::reverse() function

It reverses the order of elements in the list.

list::push_front(x)

It inserts the value x at the beginning of the list.

deleting a node from a linked list

(1) Remove the node from the list by adjusting pointers, and (2) delete it from memory.

What happens if you forget to update previous->next when inserting?

Node is disconnected; list breaks.

What happens in: head = newNode; delete newNode;

Head becomes a dangling pointer.

What does displayList(head) print if head is nullptr?

Nothing.

Why use Node*& in insert/delete functions?

It allows modifying the actual pointer passed in.

Why doesn't insert(Node* head) work?

Pointer is passed by value — changes are lost.

What happens if deleteNode can't find the value?

Nothing happens if code checks for nullptr.

What happens if you delete head without updating it?

Dangling pointer — undefined behavior.

How do you prevent infinite loop in list traversal?

Use while(current != nullptr).

What's the risk in circular linked lists?

Potential infinite loop — must break manually.

What happens if prev or next isn't updated in a doubly linked list?

Corrupts one or both traversal directions.

What does list::reverse() do?

Reverses the element order in the STL list.