Implementing a Linked List

Implementing a Linked List

How do you Program a Linked List?

• To recap the main operations of Linked Lists and how they work, follow this link
• To program a Linked List you must be able to perform the following operations:
  • Create a Linked List
  • Traverse a Linked List
  • Add data to a Linked List
  • Remove data from a Linked List

Create a Linked List

• Define the class called ‘Node’ that represents a node in the linked list.
• Each node has 2 fields ‘fruit’ (this stores the fruit value) and ‘next’ (this stores a reference to the next node in the list)
• We create 3 nodes and assign fruit values to each node
• To establish a connection between the nodes we set the ‘next’ field of each node to the appropriate next node

Pseudocode

class Node:
    field fruit
    field next

# Create nodes
node1 = Node()
node2 = Node()
node3 = Node()

# Assign fruit values
node1.fruit = "apple"
node2.fruit = "banana"
node3.fruit = "orange"

# Connect nodes
node1.next = node2
node2.next = node3
node3.next = None

Python

class Node:
    def __init__(self, fruit):
        self.fruit = fruit
        self.next = None

# Create nodes
node1 = Node("apple")
node2 = Node("banana")
node3 = Node("orange")

# Connect nodes
node1.next = node2
node2.next = node3

Java

class Node {
    String fruit;
    Node next;
    
    Node(String fruit) {
        this.fruit = fruit;
        this.next = null;
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        // Create nodes
        Node node1 = new Node("apple");
        Node node2 = new Node("banana");
        Node node3 = new Node("orange");
        
        // Connect nodes
        node1.next = node2;
        node2.next = node3;
    }
}

Algorithm to Traverse a Linked List

• We traverse the linked list starting from ‘node1’. We output the fruit value of each node and update the ‘current’ reference to the next node until we reach the end of the list

Pseudocode

# Traverse the linked list
current = node1
while current is not None:
    print(current.fruit)
    current = current.next

Python

# Traverse the linked list
current = node1
while current is not None:
    print(current.fruit)
    current = current.next

Java

// Traverse the linked list
current = node1;
while (current != null) {
    System.out.println(current.fruit);
    current = current.next;
}

Algorithm to Add Data to a Linked List

• We create a new node with the new data and check if the list is empty
• If it isn’t, we find the last node and add the new node to the end

Pseudocode

# Add "orange" to the end of the linked list
new_node = Node()
new_node.fruit = "orange"
new_node.next = None

if node1 is None:
    # If the list was empty, make "orange" the head
    node1 = new_node
else:
    # Find the last node and append "orange" to it
    current = node1
    while current.next is not None:
        current = current.next
    current.next = new_node

Python

# Add "orange" to the end of the linked list
new_node = Node("orange")

if node1 is None:
    # If the list was empty, make "orange" the head
    node1 = new_node
else:
    # Find the last node and append "orange" to it
    current = node1
    while current.next is not None:
        current = current.next
    current.next = new_node

Java

// Add "orange" to the end of the linked list
Node new_node = new Node("orange");

if (node1 == null) {
    // If the list was empty, make "orange" the head
    node1 = new_node;
} else {
    // Find the last node and append "orange" to it
    current = node1;
    while (current.next != null) {
        current = current.next;
    }
    current.next = new_node;
}

Algorithm to Remove Data from a Linked List

• We traverse the list until we find the data to be removed
• If the data to be removed is the first node, we update the head, else we update the node before to bypass the data to be removed

Pseudocode

# Find and remove "apple"
while current is not None:
    if current.fruit == "apple":
        if previous is None:
            # If "apple" is the first node, update the head
            node1 = current.next
        else:
            # Remove the node by updating the previous node's next pointer
            previous.next = current.next
        break
    previous = current
    current = current.next

Python

# Find and remove "apple"
while current is not None:
    if current.fruit == "apple":
        if previous is None:
            # If "apple" is the first node, update the head
            node1 = current.next
        else:
            # Remove the node by updating the previous node's next pointer
            previous.next = current.next
        break
    previous = current
    current = current.next

Java

// Find and remove "apple"
while (current != null) {
    if (current.fruit.equals("apple")) {
        if (previous == null) {
            // If "apple" is the first node, update the head
            node1 = current.next;
        } else {
            // Remove the node by updating the previous node's next pointer
            previous.next = current.next;
        }
        break;
    }
    previous = current;
    current = current.next;
}