Linked Lists

Question 1

Linked List

Answer 1

A data structure that represents a sequence of nodes. If you’d like to find the Kth element in the list, you will need to iterate through K elements.

Question 2

Singly Linked List

Answer 2

Each node points to the next node in the linked list.

Question 3

Doubly Linked List

Answer 3

Each node points to both the next node and the previous node.

Question 4

Create a Linked List w/ Node class

Answer 4

Access the linked list through a refrence to the head Node. Store data and next Node within one Node. Be careful when multiple objects need a reference to the linked list. If the head of the linked list changes, some objects might still point to the old head. A wrapper class could contain the head as a field and resolves the issue.

Question 5

Deleting a Node from a Linked List

Answer 5

Given node n, find previous node prev and set prev.next equal to n.next. If doubly linked, update n.next.prev to n.prev. Always check for null pointer and update head/tail of linked list of necessary.

Question 6

Runner or second pointer technique

Answer 6

Iterate through linked list with two pointers simultaneously. The fast node is either ahead by a fixed amount or jumps multiple nodes for every one jump of the slow pointer.

Question 7

Recursive Problems and Linked Lists

Answer 7

If you are having trouble with a linked list problem check if recursion will work.