1. Introduction
A Linked List is a foundational data structure composed of nodes that together represent a sequence. Each node contains data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. Linked Lists find their applications in various scenarios, including the foundation of many other data structures like stacks and queues.
2. Implementation Steps
1. Define the Node class that will represent each element in the linked list.
2. Initialize the LinkedList class with a head node set to nil (indicating an empty list).
3. Implement the append method to add elements to the end of the list.
4. Implement the prepend method to add elements to the beginning of the list.
5. Implement the size method to return the number of nodes in the list.
6. Implement the at method to return the node at a given index.
7. Implement the pop method to remove the last element from the list.
8. Implement the contains? method to check if a value exists in the list.
3. Implementation in Ruby Programming
class Node
attr_accessor :value, :next_node
def initialize(value)
@value = value
@next_node = nil
end
end
class LinkedList
def initialize
@head = nil
end
# Append an element to the end of the list
def append(value)
new_node = Node.new(value)
if @head.nil?
@head = new_node
else
current = @head
current = current.next_node while current.next_node
current.next_node = new_node
end
end
# Prepend an element to the beginning of the list
def prepend(value)
new_node = Node.new(value)
new_node.next_node = @head
@head = new_node
end
# Return the size of the list
def size
count = 0
current = @head
while current
count += 1
current = current.next_node
end
count
end
# Return the node at the given index
def at(index)
current = @head
index.times do
return nil unless current.next_node
current = current.next_node
end
current
end
# Remove the last element from the list
def pop
return nil if @head.nil?
if @head.next_node.nil?
@head = nil
else
current = @head
current = current.next_node while current.next_node.next_node
current.next_node = nil
end
end
# Check if the given value exists in the list
def contains?(value)
current = @head
while current
return true if current.value == value
current = current.next_node
end
false
end
end
# Client code
ll = LinkedList.new
ll.append("A")
ll.append("B")
ll.prepend("C")
puts "Size of linked list after adding three elements: #{ll.size}" # Output: 3
puts "Element at index 1: #{ll.at(1).value}" # Output: A
ll.pop
puts "Size of linked list after popping an element: #{ll.size}" # Output: 2
puts "Does the linked list contain 'B'? #{ll.contains?('B')}" # Output: false
Output:
Size of linked list after adding three elements: 3 Element at index 1: A Size of linked list after popping an element: 2 Does the linked list contain 'B'? false
Explanation:
1. The Node class represents each element in the linked list. It has two attributes - value that stores the actual data, and next_node that points to the next node in the list.
2. The LinkedList class is initialized with a @head node set to nil, indicating the list's starting point.
3. The append method creates a new node and, if the list is empty, assigns it as the head. If the list is not empty, it iterates through the list and adds the new node to the end.
4. The prepend method creates a new node and places it at the beginning of the list by adjusting the head node.
5. The size method iterates through the list and counts the number of nodes.
6. The at method traverses the list to the specified index and returns the node found at that index.
7. The pop method removes the last node from the list by traversing it.
8. The contains? method checks if a particular value exists in the list by iterating through each node.