The linked list exercises continue! In case you missed them, be sure to check out part 1 and part 2 of this linked list series before moving forward…

## Adding an item to the start of a linked list

In this article, the first new feature we’ll implement is the ability to add new items to the *start* of the list. It’s similar to adding an item to the *end* of a list, which is why I reviewed it above.

The diagram below shows the first two nodes of a linked list. Recall that a linked list’s `head`

points to its first node and that every node points to the next one:

Here’s how you add a new node to the start of the list. The new node becomes the first node, and the former first node becomes the second node:

Here are the steps:

- Create a new node. In our implementation, newly-created nodes have a next property that points to
`null`

,`nil`

, or`None`

by default. - If the list is empty (i.e. head points to
`null`

,`nil`

, or`None`

), adding it to the list is the same thing as adding it to the start of the list. Point`head`

to the new node and you’re done. - If the list is
*not*empty, you need to do just a little more work.- Point the new node’s
`next`

property to`head`

. This makes the current first node the one that comes*after*the new node. - Point
`head`

at the new node. This makes the new node the first one in the list.

- Point the new node’s

Here’s how I implemented this in Python…

```
# Python
def add_first(self, value):
new_node = Node(value)
# If the list is empty,
# point `head` to the newly-added node
# and exit.
if self.head is None:
self.head = new_node
return
# If the list isn’t empty,
# make the current first node the second node
# and make the new node the first node.
new_node.next = self.head
self.head = new_node
```

…and here’s my JavaScript implementation:

```
# JavaScript
addFirst(value) {
let newNode = new Node(value)
// If the list is empty,
// point `head` to the newly-added node
// and exit.
if (this.head === null) {
this.head = newNode
return
}
// If the list isn’t empty,
// make the current first node the second node
// and make the new node the first node.
newNode = this.head
this.head = newNode
}
```

## Inserting a new item at a specified position in the list

So far, we’ve implemented methods to:

- Add a new item to the start of the list, and
- Add a new item to the end of the list.

Let’s do something a little more complicated: adding a new item at a specified position in the list. The position is specified using a number, where 0 denotes the first position in the list.

Here’s how you add a new node at a specified position in the list.

Here are the steps:

- The function has two parameters:
`index`

: The index where a new node should be inserted into the list, with`0`

denoting the first item.`value`

: The value that should be stored in the new node.

- Create a new node,
`new_node`

, and put`value`

into it. - Use a variable,
`current_index`

, to keep track of the index of the node we’re currently looking at as we traverse the list. It should initially be set to`0`

. - Use another variable,
`current_node`

, which will hold a reference to the node we’re currently looking at. It should initially be set to`head`

, which means that we’ll start at the first item in the list. - Repeat the following as long as
`current_node`

*is not*referencing`null`

,`nil`

, or`None`

:- We’re looking for the node in the position
*immediately before*the position where we want to insert the new node. If`current_index`

is one less than`index`

:- Point the new node at the current node’s next node.
- Point the current node at the new node.
- Return
`true`

, meaning that we successfully inserted a new item into the list

- If we’re here, it means that we haven’t yet reached the node immediately before the insertion point. Move to the next node and increment
`current_index`

.

- We’re looking for the node in the position
- If we’re here, it means that we’ve gone past the last item in the list.
`false`

, meaning we didn’t insert a new item into the list.

Here’s how I implemented this in Python…

```
# Python
def insert_element_at(self, index, value):
new_node = Node(value)
current_index = 0
current_node = self.head
# Traverse the list, keeping count of
# the nodes that you visit,
# until you’ve reached the specified node.
while current_node:
if current_index == index - 1:
# We’re at the node before the insertion point!
# Make the new node point to the next node
# and the current node point to the new node.
new_node.next = current_node.next
current_node.next = new_node
return True
# We’re not there yet...
current_node = current_node.next
current_index += 1
# If you’re here, the given index is larger
# than the number of elements in the list.
return False
```

…and here’s my JavaScript implementation:

```
// JavaScript
insertElementAt(index, value) {
let newNode = new Node(value)
let currentIndex = 0
let currentNode = this.head
// Traverse the list, keeping count of
// the nodes that you visit,
// until you’ve reached the specified node.
while (currentNode) {
if (currentIndex === index - 1) {
// We’re at the node before the insertion point!
// Make the new node point to the next node
// and the current node point to the new node.
newNode.next = currentNode.next
currentNode.next = newNode
return true
}
// We’re not there yet...
currentNode = currentNode.next
currentIndex++
}
// If you’re here, the given index is larger
// than the number of elements in the list.
return false
}
```

## Deleting an item from a specified position in the list

Now that we can add a new item at a specified position in the list, let’s implement its opposite: deleting an item from a specified position in the list. Once again, the position is specified using a number, where 0 denotes the first position in the list.

Here’s how you delete a new node from a specified position in the list:

Here are the steps:

- The function has a single parameter,
`index`

: the index of the node to be deleted, with`0`

denoting the first item in the list. - Use a variable,
`current_index`

, to keep track of the index of the node we’re currently looking at as we traverse the list. It should initially be set to`0`

. - Use another variable,
`current_node`

, which will hold a reference to the node we’re currently looking at. It should initially be set to`head`

, which means that we’ll start at the first item in the list. - Repeat the following as long as
`current_node`

*is not*referencing`null`

,`nil`

, or`None`

:- We’re looking for the node in the position
*immediately before*the position of the node we want to delete. If`current_index`

is one less than`index`

:- Point the current node to the next node’s next node, which removes the next node from the list.
- Set both the next node’s
`data`

and`next`

properties to`null`

,`nil`

, or`None`

.**At this point, this node is no longer in the list and is an “island” —**It will eventually be garbage collected.*no object points to it, and it doesn’t point to any objects.* - Return
`true`

, meaning that we successfully deleted the item from the list

- If we’re here, it means that we haven’t yet reached the node immediately before the deletion point. Move to the next node and increment
`current_index`

.

- We’re looking for the node in the position
- If we’re here, it means that we’ve gone past the last item in the list.
`false`

, meaning we didn’t delete the item from the list.

Here’s how I implemented this in Python…

```
# Python
def delete_element_at(self, index):
current_index = 0
current_node = self.head
# Traverse the list, keeping count of
# the nodes that you visit,
# until you’ve reached the specified node.
while current_node:
if current_index == index - 1:
# We’re at the node before the node to be deleted!
# Make the current node point to the next node’s next node
# and set the next node’s `data` and `next` properties
# to `None`.
delete_node = current_node.next
current_node.next = delete_node.next
delete_node.data = None
delete_node.next = None
return True
# We’re not there yet...
current_node = current_node.next
current_index += 1
# If you’re here, the given index is larger
# than the number of elements in the list.
return False
```

…and here’s my JavaScript implementation:

```
// JavaScript
deleteElementAt(index) {
let currentIndex = 0
let currentNode = this.head
// Traverse the list, keeping count of
// the nodes that you visit,
// until you’ve reached the specified node.
while (currentNode) {
if (currentIndex === index - 1) {
// We’re at the node before the node to be deleted!
// Make the current node point to the next node’s next node
// and set the next node’s `data` and `next` properties
// to `null`.
const deleteNode = currentNode.next
currentNode.next = deleteNode.next
deleteNode.data = null
deleteNode.next = null
return true
}
// We’re not there yet...
currentNode = currentNode.next
currentIndex++
}
// If you’re here, the given index is larger
// than the number of elements in the list.
return false
}
```

## The classes so far

Let’s take a look at the complete `Node`

and `LinkedList`

classes so far, in both Python and JavaScript.

### Python

```
# Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __str__(self):
return f"{self.data}"
class LinkedList:
def __init__(self):
self.head = None
def __str__(self):
if self.head is None:
return('Empty list.')
result = ""
current_node = self.head
while current_node:
result += f'{current_node}\n'
current_node = current_node.next
return result.strip()
def add_last(self, value):
new_node = Node(value)
# If the list is empty,
# point `head` to the newly-added node
# and exit.
if self.head is None:
self.head = new_node
return
# If the list isn’t empty,
# traverse the list by going to each node’s
# `next` node until there isn’t a `next` node...
current_node = self.head
while current_node.next:
current_node = current_node.next
# If you’re here, `current_node` is
# the last node in the list.
# Point `current_node` at
# the newly-added node.
current_node.next = new_node
def __len__(self):
count = 0
current_node = self.head
# Traverse the list, keeping count of
# the nodes that you visit,
# until you’ve gone past the last node.
while current_node:
current_node = current_node.next
count += 1
return count
def get_element_at(self, index):
current_index = 0
current_node = self.head
# Traverse the list, keeping count of
# the nodes that you visit,
# until you’ve reached the specified node.
while current_node:
if current_index == index:
# We’re at the node at the given index!
return current_node.data
# We’re not there yet...
current_node = current_node.next
current_index += 1
# If you’re here, the given index is larger
# than the number of elements in the list.
return None
def set_element_at(self, index, value):
current_index = 0
current_node = self.head
# Traverse the list, keeping count of
# the nodes that you visit,
# until you’ve reached the specified node.
while current_node:
if current_index == index:
# We’re at the node at the given index!
current_node.data = value
return True
# We’re not there yet...
current_node = current_node.next
current_index += 1
# If you’re here, the given index is larger
# than the number of elements in the list.
return False
def add_first(self, value):
new_node = Node(value)
# If the list is empty,
# point `head` to the newly-added node
# and exit.
if self.head is None:
self.head = new_node
return
# If the list isn’t empty,
# make the current first node the second node
# and make the new node the first node.
new_node.next = self.head
self.head = new_node
def insert_element_at(self, index, value):
new_node = Node(value)
current_index = 0
current_node = self.head
# Traverse the list, keeping count of
# the nodes that you visit,
# until you’ve reached the specified node.
while current_node:
if current_index == index - 1:
# We’re at the node before the insertion point!
# Make the new node point to the next node
# and the current node point to the new node.
new_node.next = current_node.next
current_node.next = new_node
return True
# We’re not there yet...
current_node = current_node.next
current_index += 1
# If you’re here, the given index is larger
# than the number of elements in the list.
return False
def delete_element_at(self, index):
current_index = 0
current_node = self.head
# Traverse the list, keeping count of
# the nodes that you visit,
# until you’ve reached the specified node.
while current_node:
if current_index == index - 1:
# We’re at the node before the node to be deleted!
# Make the current node point to the next node’s next node
# and set the next node’s `data` and `next` properties
# to `None`.
delete_node = current_node.next
current_node.next = delete_node.next
delete_node.data = None
delete_node.next = None
return True
# We’re not there yet...
current_node = current_node.next
current_index += 1
# If you’re here, the given index is larger
# than the number of elements in the list.
return False
```

### JavaScript

```
// JavaScript
class Node {
constructor(data) {
this.data = data
this.next = null
}
toString() {
return this.data.toString()
}
}
class LinkedList {
constructor() {
this.head = null
}
toString() {
if (!this.head) {
return('Empty list.')
}
let output = ""
let currentNode = this.head
while (currentNode) {
output += `${currentNode.data.toString()}\n`
currentNode = currentNode.next
}
return output.trim()
}
addLast(value) {
let newNode = new Node(value)
// If the list is empty,
// point `head` to the newly-added node
// and exit.
if (this.head === null) {
this.head = newNode
return
}
// If the list isn’t empty,
// traverse the list by going to each node’s
// `next` node until there isn’t a `next` node...
let currentNode = this.head
while (currentNode.next) {
currentNode = currentNode.next
}
// If you’re here, `currentNode` is
// the last node in the list.
// Point `currentNode` at
// the newly-added node.
currentNode.next = newNode
}
getCount() {
let count = 0
let currentNode = this.head
// Traverse the list, keeping count of
// the nodes that you visit,
// until you’ve gone past the last node.
while (currentNode) {
currentNode = currentNode.next
count++
}
return count
}
getElementAt(index) {
let currentIndex = 0
let currentNode = this.head
// Traverse the list, keeping count of
// the nodes that you visit,
// until you’ve reached the specified node.
while (currentNode) {
if (currentIndex === index) {
// We’re at the node at the given index!
return currentNode.data
}
// We’re not there yet...
currentNode = currentNode.next
currentIndex++
}
// If you’re here, the given index is larger
// than the number of elements in the list.
return null
}
setElementAt(index, value) {
let currentIndex = 0
let currentNode = this.head
// Traverse the list, keeping count of
// the nodes that you visit,
// until you’ve reached the specified node.
while (currentNode) {
if (currentIndex === index) {
// We’re at the node at the given index!
currentNode.data = value
return true
}
// We’re not there yet...
currentNode = currentNode.next
currentIndex++
}
// If you’re here, the given index is larger
// than the number of elements in the list.
return false
}
addFirst(value) {
let newNode = new Node(value)
// If the list is empty,
// point `head` to the newly-added node
// and exit.
if (this.head === null) {
this.head = newNode
return
}
// If the list isn’t empty,
// make the current first node the second node
// and make the new node the first node.
newNode = this.head
this.head = newNode
}
insertElementAt(index, value) {
let newNode = new Node(value)
let currentIndex = 0
let currentNode = this.head
// Traverse the list, keeping count of
// the nodes that you visit,
// until you’ve reached the specified node.
while (currentNode) {
if (currentIndex === index - 1) {
// We’re at the node before the insertion point!
// Make the new node point to the next node
// and the current node point to the new node.
newNode.next = currentNode.next
currentNode.next = newNode
return true
}
// We’re not there yet...
currentNode = currentNode.next
currentIndex++
}
// If you’re here, the given index is larger
// than the number of elements in the list.
return false
}
deleteElementAt(index) {
let currentIndex = 0
let currentNode = this.head
// Traverse the list, keeping count of
// the nodes that you visit,
// until you’ve reached the specified node.
while (currentNode) {
if (currentIndex === index - 1) {
// We’re at the node before the node to be deleted!
// Make the current node point to the next node’s next node
// and set the next node’s `data` and `next` properties
// to `null`.
const deleteNode = currentNode.next
currentNode.next = deleteNode.next
deleteNode.data = null
deleteNode.next = null
return true
}
// We’re not there yet...
currentNode = currentNode.next
currentIndex++
}
// If you’re here, the given index is larger
// than the number of elements in the list.
return false
}
}
```

## Coming up next

It’s time to reverse that list!

## Previously in this series

- How to solve coding interview questions: Linked lists, part 2
- How to solve coding interview questions: Linked lists, part 1
- How to solve coding interview questions: Finding the first NON-recurring character in a string in Swift
- How to solve coding interview questions: Looking deeper into finding the first NON-recurring character in a string
- How to solve coding interview questions: The first NON-recurring character in a string
- Coding interview questions: “First recurring character” in Swift
- How to solve coding interview questions: The first recurring character in a string
- I Has the Dumb (or: How I Embarrassed Myself in My Interview with Google) — from way back in 2013