I have pretty much covered the linked list, at least for now. I know there is more stuff to add. This was interesting to revisit, and I started at the beginning of mod3 and am finishing it in mod4. Going through this, there are some things I would definitely change, but this is an interesting look into how my education has gone (at some point I became much more aware of testing for edge cases, for example). So I am going to link all of the articles here, and then below I will share the whole Linked List class, if anyone is curious. Next week marks the final project, and I am working in a new language. So I will either be writing about switching to python, or C#, not sure which one yet. As always, please let me know if I missed anything, or did something wrong/you know a better way.
Methods
class LinkedList
attr_accessor :head
def initialize
@head = nil
end
def empty?
head.nil?
end
def append(data)
if empty?
@head = Node.new(data)
else
current_node = head
while current_node.next_node != nil
current_node = current_node.next_node
end
current_node.next_node = Node.new(data)
end
end
def count
return 0 if empty?
count = 1
current_node = head
while current_node.next_node != nil
current_node = current_node.next_node
count += 1
end
count
end
def stringify
new_string = []
current_node = head
return new_string if empty?
while current_node.next_node != nil
new_string << current_node.data
current_node = current_node.next_node
end
new_string << current_node.data
new_string.join(", ")
end
def prepend(data)
new_node = Node.new(data)
new_node.next_node = head
@head = new_node
end
def node_at(index, counter = 0)
return nil if index < 0
current_node = head
while counter < index
return nil if current_node.nil?
current_node = current_node.next_node
counter += 1
end
current_node
end
def insert(location, data)
if location == 0
prepend(data)
return
end
new_node = Node.new(data)
prior_node = node_at(location - 1)
raise "Invalid location" if prior_node.nil?
next_node = node_at(location)
prior_node.next_node = new_node
new_node.next_node = next_node
# return new_node
end
def pop
return nil if head.nil?
if head.next_node.nil?
tail_data = head.data
self.head = nil
return tail_data
end
new_tail = node_at(count - 2)
old_tail = new_tail.next_node
new_tail.next_node = nil
return old_tail.data
end
def shift
return nil if head.nil?
former_head = head
@head = head.next_node
return former_head.data
end
def find(start, how_many)
return nil if head.nil? || how_many < 0 || start > count
counter = 0
new_string = []
current_node = node_at(start)
return current_node.data if how_many == 1
while counter < how_many && current_node
new_string << current_node.data
current_node = current_node.next_node
counter += 1
end
new_string.join(", ")
end
def includes?(data)
return false if head.nil?
current_node = head
while current_node != nil
return true if current_node.data == data
current_node = current_node.next_node
end
false
end
end
Tests
require './lib/node'
require './lib/linked_list'
RSpec.describe LinkedList do
describe 'initialize' do
it 'exists' do
list = LinkedList.new
expect(list).to be_instance_of(LinkedList)
end
it 'has a head' do
list = LinkedList.new
expect(list.head).to eq(nil)
end
end
describe '#empty?' do
it 'it is empty' do
list = LinkedList.new
expect(list.empty?).to eq(true)
end
end
describe 'append' do
it 'can append one thing' do
list = LinkedList.new
list.append("A")
expect(list.head.data).to eq("A")
expect(list.head.next_node).to eq(nil)
end
it 'can append more than one' do
list = LinkedList.new
list.append("A")
expect(list.head.data).to eq("A")
expect(list.head.next_node).to eq(nil)
list.append("B")
expect(list.head.next_node.data).to eq("B")
end
it 'can append more than one' do
list = LinkedList.new
list.append("A")
expect(list.head.data).to eq("A")
expect(list.head.next_node).to eq(nil)
list.append("B")
expect(list.head.next_node.data).to eq("B")
list.append("C")
expect(list.head.next_node.next_node.data).to eq("C")
end
end
describe 'count' do
it 'can be counted' do
list = LinkedList.new
list.append("A")
expect(list.count).to eq(1)
end
it 'can count to 3' do
list = LinkedList.new
list.append("A")
list.append("B")
list.append("C")
expect(list.count).to eq(3)
end
it 'returns 0 if count is 0' do
list = LinkedList.new
expect(list.count).to eq(0)
end
end
describe 'stringify' do
it 'can be turned into a string' do
list = LinkedList.new
list.append("A")
expect(list.stringify).to eq("A")
end
it 'can turn multiple data points into a string' do
list = LinkedList.new
list.append("A")
list.append("B")
list.append("C")
list.append("D")
expect(list.stringify).to eq("A, B, C, D")
end
it 'returns 0 if count is 0' do
list = LinkedList.new
expect(list.stringify).to eq([])
end
end
describe 'prepend' do
it 'adds something at the beginning' do
list = LinkedList.new
list.append("B")
list.append("C")
list.append("D")
expect(list.stringify).to eq("B, C, D")
list.prepend("A")
expect(list.stringify).to eq("A, B, C, D")
end
end
describe 'node_at' do
it 'tells you what a node contains' do
list = LinkedList.new
list.append('a')
list.append('b')
list.append('c')
list.append('d')
list.append('e')
node = list.node_at(3)
expect(node.data).to eq('d')
end
it 'cant search for a negative number' do
list = LinkedList.new
list.append('a')
list.append('b')
expect(list.node_at(-1)).to eq(nil)
end
it 'returns nil if the node does not exist' do
list = LinkedList.new
list.append('a')
list.append('b')
expect(list.node_at(5)).to eq(nil)
end
end
describe 'insert' do
it "needs to be able to insert at a specific point" do
list = LinkedList.new
list.append('a')
list.append('b')
list.append('c')
list.append('e')
list.append('f')
expect(list.stringify).to eq("a, b, c, e, f")
list.insert(3, 'd')
expect(list.stringify).to eq("a, b, c, d, e, f")
end
it 'returns a message if you can not insert it' do
list = LinkedList.new
expect { list.insert(15, 'd') }.to raise_error(RuntimeError, "Invalid location")
end
end
describe 'pop' do
it "removes last element and returns it" do
list = LinkedList.new
list.append("a")
list.append("b")
list.append("c")
list.append("d")
list.append("e")
expect(list.pop).to eq("e")
expect(list.stringify).to eq("a, b, c, d")
expect(list.pop).to eq("d")
expect(list.stringify).to eq("a, b, c")
end
it "returns nil when called on an empty list" do
list = LinkedList.new
expect(list.pop).to be_nil
end
it "correctly handles a list with a single element" do
list = LinkedList.new
list.append("a")
expect(list.pop).to eq("a")
expect(list.stringify).to eq([])
end
end
describe 'shift' do
it "removes first element and returns it" do
list = LinkedList.new
list.append("a")
list.append("b")
list.append("c")
list.append("d")
list.append("e")
expect(list.shift).to eq("a")
expect(list.stringify).to eq("b, c, d, e")
expect(list.shift).to eq("b")
expect(list.stringify).to eq("c, d, e")
end
it "returns nil when called on an empty list" do
list = LinkedList.new
expect(list.shift).to be_nil
end
it "correctly handles a list with a single element" do
list = LinkedList.new
list.append("a")
expect(list.shift).to eq("a")
expect(list.stringify).to eq([])
end
end
describe 'find' do
it "indicates where to look and how many to return" do
list = LinkedList.new
list.append("a")
list.append("b")
list.append("c")
list.append("d")
list.append("e")
expect(list.find(2, 1)).to eq("c")
end
it "1st parameter indicates where to start and second specifies how many to return (multiple return)" do
list = LinkedList.new
list.append("a")
list.append("b")
list.append("c")
list.append("d")
list.append("e")
expect(list.find(1, 2)).to eq("b, c")
expect(list.find(1, 3)).to eq("b, c, d")
end
it "returns nil if starting index is out of bounds" do
list = LinkedList.new
list.append("a")
list.append("b")
expect(list.find(5, 1)).to be_nil
end
it "returns nil if the list is empty" do
list = LinkedList.new
expect(list.find(0, 1)).to be_nil
end
it "if more elements requested than are available" do
list = LinkedList.new
list.append("a")
list.append("b")
list.append("c")
expect(list.find(1, 5)).to eq("b, c")
end
it "returns an empty string if number of elements to return is zero" do
list = LinkedList.new
list.append("a")
list.append("b")
expect(list.find(1, 0)).to eq("")
end
it "returns nil if number of elements to return is negative" do
list = LinkedList.new
list.append("a")
list.append("b")
expect(list.find(1, -1)).to be_nil
end
end
describe 'includes' do
it "gives true or false if the value is in the list" do
list = LinkedList.new
list.append("a")
list.append("b")
list.append("c")
list.append("d")
list.append("e")
expect(list.includes?("a")).to be true
expect(list.includes?("f")).to be false
end
it "returns false when the list is empty" do
list = LinkedList.new
expect(list.includes?("anything")).to be false
end
end
end
Leave a Reply