# A.1.5: Linked Lists

- 1.Linked lists store ordered data using nodes that each contain a payload and a pointer to the next node
- 2.A pointer is a memory address, called "pointer" for illustration purposes
- 3.When to use linked lists vs arrays
- 4.How to execute common linked list operations such as inserting and deleting nodes

Brief introduction to the linked list data structure. Source: Neso Academy

Linked lists store ordered lists of data where elements (aka "nodes") may not be stored in contiguous blocks of memory. Each node contains a payload (numbers in above illustration) and a pointer to the next node (arrows in above illustration).

The benefit of non-contiguous data is that inserting or deleting a node from anywhere in a linked list is an

`O(1)`

operation because only adjacent nodes need updating, instead of all subsequent elements in an array. The drawback of this is that accessing an element in the middle of a linked list requires `O(n)`

traversal, instead of `O(1)`

access with an array.Below is a comparison of runtimes for common array and linked list operations.

Operation | Runtime (Arrays) | Runtime (Linked Lists) |
---|---|---|

Insertion/Deletion (start) | `O(n)` | `O(1)` |

Insertion/Deletion (middle) | `O(n)` | `O(n)` (`O(1)` if we have pointer to the node to be deleted) |

Insertion/Deletion (end) | `O(1)` | `O(n)` (`O(1)` if we have pointer to tail node with doubly-linked list) |

Access element at specific index | `O(1)` | `O(n)` |

We typically use linked lists when we need efficient deletion of the first element in a list, for example to implement queues. We also use linked lists when we may not have sufficient contiguous storage space, for example in file systems on our hard drives.

The following linked list node definition is the definition LeetCode uses for linked list problems. Each node will have 2 properties

`val`

and `next`

that can be accessed with dot notation like with any other class instance, e.g. `node.val`

and `node.next`

, where `node`

is a `ListNode`

instance.function ListNode(val, next) {

this.val = val === undefined ? 0 : val;

this.next = next === undefined ? null : next;

}

Given a linked list head node

`node`

, we can traverse the linked list with a while loop and calling `node = node.next`

at the end of the loop, where `next`

is a property of the linked list node that points to the next node.while (node) {

// TODO: Do something with current node

node = node.next; // Iterate to next node

}

Steps to insert a node in a linked list. Source: University of San Francisco

To insert a node in a linked list we need to:

- 1.Point the "next" pointer in the new node to the node ahead of it in the list
- 2.Point the "next" pointer of the node behind the new node to the new node

To delete a node in a linked list we need to:

- 1.Point the "next" pointer of the previous node to the node after the current node, effectively removing the current node from the chain of nodes in the linked list

After attempting each problem, find solutions in the Leaderboard tab (HackerRank, may be on left side of page) or Solution or Discuss tabs (LeetCode) on that problem's page. If you get stuck for more than 15 minutes, review and understand the solutions and move on. Come back and re-attempt the problem after a few days.

For problems with both HackerRank and LeetCode, implement a solution on the platform you are least comfortable with; feel free to submit on both.

- 1.
- 2.

- 1.
- 2.
- 3.
- 4.

- 1.
- 2.
- 3.
- 4.

- 1.
- 2.
- 1.Hint: Keep track of prev node and next node. When we encounter duplicate, update prev node's next value to next node

- 3.
- 4.
- 1.Hint: For given node, keep track of old next node and new next node
- 2.Hint: Inside while loop:
- 1.Old next node is
`node.next`

- 2.Assign
`node.next`

to new next node (the node we just visited) - 3.Assign new next node variable to
`node`

- 4.Assign
`node`

to old next node

- 1.
- 2.
- 3.
- 4.

Last modified 1yr ago