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.
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.
- If we’re here, it means that we’ve gone past the last item in the list.
Return 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” — no object points to it, and it doesn’t point to any objects. It will eventually be garbage collected. - 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.
- If we’re here, it means that we’ve gone past the last item in the list.
Return 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
