Ch 2: Linked Lists

Question 1

What is a
Linked List?

Answer 1

A data structure that represents a sequence of nodes, with each node pointing to the next node in the list or null.

Question 2

Two basic types of Linked List

Answer 2

Singly Linked List:
Each node points to next node

Doubly Linked List:
Each node points to next node and previous node

Question 3

Time Complexity:
Access time of Linked List
vs
Array

Answer 3

To find the Kth element in a Linked List, need to iterate through K elements.
Linked List Access Time is O(n)

An array provides constant access time, O(1) by using an index

Question 4

Benefit of Linked List

Answer 4

Items can be added and removed from the beginning of the list, or anywhere else, in constant time O(1).
This can be very useful for specific applications.

Question 5

Linked List:
Operations

Answer 5

• Creating a Linked List
• Appending a new node
• Accessing a node
• Removing a node

Question 6

Linked List:
Basic Structure

Answer 6

• Node class:
  pointer to data
  pointers to Node(s)

First Node is considered the “Head”
Basic Implementation accessed by the Head.

Better implementations creates a LinkedList class as a wrapper.

Question 7

Linked List:
Benefit of “wrapper” class
over bare Head Node

Answer 7

With just a reference to the head node,
objects might store the reference to it, but these references wouldn’t be updated if the head node changes. Some objects might still point at the old head.

Using a LinkedList class to wrap the Node class provides a reference that doesn’t change when head changes.

Question 8

Operation:
Deleting a Node from a Singly Linked List

Answer 8

To delete a node, n :

Find the previous node, where prev.next == n
Set prev.next = n.next
deallocate node n (if language requires memory management)

Question 9

Operation:
Deleting a Node from a Doubly Linked List

Answer 9

Very similar to deleting from Singly Linked List
To delete a node, n :

Find the previous node, where prev.next == n
Set prev.next = n.next
Set n.next.prev = prev
deallocate node n (if language requires memory management)

Question 10

“Runner” Technique
Basic Concept

Answer 10

Iterate through a Linked List with two pointers simultaneously.
“Slow” pointer moves normally, single node at a time
“Fast” pointer either moves ahead by a fixed amount, or hops multiple nodes at once.

Question 11

Linked List Problem Approaches:
Recursive Problems

Answer 11

• A number of linked list problems rely on recursion
• Remember that recursive algorithms take at least O(n) space due to the depth of the recursive call.
• With space constraints, it may be better to implement an iterative approach

Question 12

True or False:
Many recursive algorithms cannot be implemented iteratively.

Answer 12

False:
All recursive algorithms can be implemented iteratively, but they may be much more complex.