Linked Lists

My OOP implementation of linked lists in ruby.

Background

Linked lists are one of the most basic and fundamental data structures in computer science. The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation of any other elements.

A linked list is a linear collection of data elements called nodes that “point” to the next node by means of a pointer.
Each node holds a single element of data and a link or pointer to the next node in the list.
A head node is the first node in the list, a tail node is the last node in the list. Below is a basic representation of a linked list: [ NODE(head) ] -> [ NODE ] -> [ NODE(tail) ] -> nil

Implementation

Two classes:

LinkedList class, which will represent the full list.
Node class, containing a #value method and a link to the #next_node, set both as nil by default.

Methods

#append(value) adds a new node containing value to the end of the list
#prepend(value) adds a new node containing value to the start of the list
#size returns the total number of nodes in the list
#head returns the returns the first node in the list
#tail returns the last node in the list
#at(index) returns the node at the given index
#pop removes the last element from the list
#contains?(value) returns true if the passed in value is in the list and otherwise returns false.
#find(value) returns the index of the node containing value, or nil if not found.
#to_s represent LinkedList objects as strings, so you can print them out and preview them in the console. The format should be: ( value ) -> ( value ) -> ( value ) -> nil
#insert_at(value, index) that inserts a new node with the provided value at the given index.
#remove_at(index) that removes the node at the given index.

Code

# Node class
class Node
  attr_accessor :value, :next_node

  def initialize(value = nil)
    @value = value
    @next_node = nil
  end
end

# LinkedList class
class LinkedList
  attr_reader :head

  def initialize(node = nil)
    @head = node
  end

  def append(val)
    current = @head
    current = current.next_node until current.next_node.nil?
    current.next_node = Node.new(val)
  end

  def prepend(val)
    new_head = Node.new(val)
    new_head.next_node = @head
    @head = new_head
  end

  def size
    current = @head
    count = current.nil? ? 0 : 1
    until current.next_node.nil?
      count += 1
      current = current.next_node
    end
    count
  end

  def tail
    return nil if @head.nil?

    current = @head
    loop do
      break if current.next_node.nil?

      current = current.next_node
    end
    current
  end

  def at(index)
    return nil if @head.nil?
    return nil if index > size - 1

    current = @head
    i = 0
    loop do
      break if current.next_node.nil? || index == i

      current = current.next_node
      i += 1
    end
    current.value
  end

  def pop
    return nil if @head.nil?

    if @head.next_node.nil?
      removed = @head
      @next_node = nil
      return removed
    end

    current = @head
    loop do
      break if current.next_node.next_node.nil?

      current = current.next_node
    end
    removed = current.next_node
    current.next_node = nil
    removed
  end

  def contains?(value)
    current = @head
    until current.nil?
      return true if current.value == value

      current = current.next_node
    end
    false
  end

  def find(value)
    current = @head
    i = 0
    until current.nil?
      break if current.value == value

      current = current.next_node
      i += 1
    end
    i
  end

  def to_s
    str = ''
    current = @head
    until current.nil?
      str << if current.value.nil?
               '( nil ) => '
             else
               "( #{current.value} ) => "
             end
      current = current.next_node
    end
    str << 'nil'
  end

  def insert_at(value, index)
    if @head.nil?
      @head = Node.new(value)
      return
    end

    if index.zero?
      node = Node.new(value)
      node.next_node = @head.next_node
      @head = node
      return
    end

    previous = current = @head
    i = 0
    loop do
      break if index == i

      append(nil) if current.next_node.nil?

      previous = current
      current = current.next_node
      i += 1
    end
    node = Node.new(value)
    previous.next_node = node
    node.next_node = current.next_node
  end

  def remove_at(index)
    return nil if @head.nil?
    return nil if index > size - 1

    if index.zero?
      removed = @head
      @head = @head.next_node
      return removed
    end

    previous = @head
    current = @head
    i = 0
    loop do
      break if current.next_node.nil? || index == i

      previous = current
      current = current.next_node
      i += 1
    end
    if current.next_node.nil?
      removed = nil
    else
      removed = current.next_node
      previous.next_node = current.next_node
    end
    removed
  end
end

Example Usage

# Creates a linked list (0)->(1)->(5)->(3)->(4)
ist = LinkedList.new(Node.new(1))
list.append(5)
list.append(3)
list.append(4)
list.prepend(0)

# Print the linked list and size
puts list.to_s
puts list.size

# Return head and tail
p list.head
p list.tail

# Return the node at index 3 and 20
p list.at(3)
p list.at(20)

# Pop a node off the end
puts list.to_s
list.pop
puts list.to_s

# Check which values are present
Array((-5..5)).each { |x| puts "#{x} in list? : #{list.contains?(x)}" }

# Find the index of first matching value
p list.find(0)
p list.find(3)

# Remove the value at index 1
p list.to_s
list.remove_at(1)
p list.to_s

# Remove the value at index 0
p list.remove_at(0)
p list.to_s

# Insert a value 777 at index 10 (new linked-list should have size 11)
p list.insert_at(777, 10)
p list.to_s
p list.size

# Insert 4 @ 6, 3 @ 2, 55 @ 1, and 10 @ 0
p list.insert_at(4, 6)
p list.insert_at(3, 2)
p list.insert_at(55, 1)
p list.insert_at(10, 0)
p list.to_s

Example Output

( 0 ) => ( 1 ) => ( 5 ) => ( 3 ) => ( 4 ) => nil
5
#<Node:0x00007f25c936cef0 @value=0, @next_node=#<Node:0x00007f25c936d170 @value=1, @next_node=#<Node:0x00007f25c936d008 @value=5, @next_node=#<Node:0x00007f25c936cf90 @value=3, @next_node=#<Node:0x00007f25c936cf68 @value=4, @next_node=nil>>>>>
#<Node:0x00007f25c936cf68 @value=4, @next_node=nil>
3
nil
( 0 ) => ( 1 ) => ( 5 ) => ( 3 ) => ( 4 ) => nil
( 0 ) => ( 1 ) => ( 5 ) => ( 3 ) => nil
-5 in list? : false
-4 in list? : false
-3 in list? : false
-2 in list? : false
-1 in list? : false
0 in list? : true
1 in list? : true
2 in list? : false
3 in list? : true
4 in list? : false
5 in list? : true
0
3
"( 0 ) => ( 1 ) => ( 5 ) => ( 3 ) => nil"
"( 0 ) => ( 5 ) => ( 3 ) => nil"
#<Node:0x00007f25c936cef0 @value=0, @next_node=#<Node:0x00007f25c936d008 @value=5, @next_node=#<Node:0x00007f25c936cf90 @value=3, @next_node=nil>>>
"( 5 ) => ( 3 ) => nil"
nil
"( 5 ) => ( 3 ) => ( nil ) => ( nil ) => ( nil ) => ( nil ) => ( nil ) => ( nil ) => ( nil ) => ( nil ) => ( 777 ) => nil"
11
#<Node:0x00007f25c9376860 @value=nil, @next_node=#<Node:0x00007f25c9376810 @value=nil, @next_node=#<Node:0x00007f25c93767e8 @value=nil, @next_node=#<Node:0x00007f25c93766f8 @value=777, @next_node=nil>>>>
#<Node:0x00007f25c9376928 @value=nil, @next_node=#<Node:0x00007f25c9376900 @value=nil, @next_node=#<Node:0x00007f25c93768b0 @value=nil, @next_node=#<Node:0x00007f25c9375a28 @value=4, @next_node=#<Node:0x00007f25c9376860 @value=nil, @next_node=#<Node:0x00007f25c9376810 @value=nil, @next_node=#<Node:0x00007f25c93767e8 @value=nil, @next_node=#<Node:0x00007f25c93766f8 @value=777, @next_node=nil>>>>>>>>
#<Node:0x00007f25c9375398 @value=3, @next_node=#<Node:0x00007f25c9376928 @value=nil, @next_node=#<Node:0x00007f25c9376900 @value=nil, @next_node=#<Node:0x00007f25c93768b0 @value=nil, @next_node=#<Node:0x00007f25c9375a28 @value=4, @next_node=#<Node:0x00007f25c9376860 @value=nil, @next_node=#<Node:0x00007f25c9376810 @value=nil, @next_node=#<Node:0x00007f25c93767e8 @value=nil, @next_node=#<Node:0x00007f25c93766f8 @value=777, @next_node=nil>>>>>>>>>
nil
"( 10 ) => ( 55 ) => ( 3 ) => ( nil ) => ( nil ) => ( nil ) => ( 4 ) => ( nil ) => ( nil ) => ( nil ) => ( 777 ) => nil"

kckuei / odin-linked-lists Goto Github PK

odin-linked-lists's Introduction

Linked Lists

Background

Implementation

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent