How to program a single linked list in crystal explicitly

Help & Support
1

I found the following code but i compiles and runs in no way.


struct Node
  property data : Int32
  property next : Node?

  def initialize(@data : Int32, @next : Node? = nil)
  end
end

struct LinkedList
  property head : Node?

  def initialize(@head : Node? = nil)
  end

  # Add a node to the beginning of the list
  def push(data : Int32)
    new_node = Node.new(data, @head)
    @head = new_node
  end

  # Remove the first node from the list
  def pop
    if @head.nil?
      return nil
    end

    removed_node = @head
    @head = @head.next
    removed_node.next = nil
    removed_node.data
  end

  # Delete a node with a given data value
  def delete(data : Int32)
    if @head.nil?
      return
    end

    if @head.data == data
      @head = @head.next
      return
    end

    current_node = @head
    while current_node.next != nil
      if current_node.next.data == data
        current_node.next = current_node.next.next
        return
      end
      current_node = current_node.next
    end
  end

  # Print the list
  def print
    current_node = @head
    while current_node != nil
      print current_node.data, " "
      current_node = current_node.next
    end
    puts
  end
end

# Example usage:
list = LinkedList.new
list.push(10)
list.push(20)
list.push(30)
list.print # Output: 30 20 10

list.delete(20)
list.print # Output: 30 10

list.pop
list.print # Output: 30

Any advice is appreciated.

2

Hi
It looks like next being nilable might require you to use not_nil! in several places.
Also, using Struct for a LinkedList might not work well in this case. You may have run into an error like this:

recursive struct Node detected
`@next : (Node | Nil)` -> `(Node | Nil)` -> `Node`
The struct Node has, either directly or indirectly,
an instance variable whose type is, eventually, this same
struct. This makes it impossible to represent the struct
in memory, because the size of this instance variable depends
on the size of this struct, which depends on the size of
this instance variable, causing an infinite cycle.
You should probably be using classes here, as classes
instance variables are always behind a pointer, which makes
it possible to always compute a size for them.

This happens because Struct can’t handle recursive data structures properly.
Switching to a Class might work better here.

By the way, what is your goal with implementing a LinkedList?

3

As the name suggests, a linked list is build with links. But this implementation doesn’t link nodes. It uses structs and tries to embed them inside each other, which obviously cannot work.
Linked list need to be built using references, either based on a reference type (i.e. class) or when using value types (i.e. struct), you need to explicitly manage node pointers.
For inspiration you could take a look at the stdlib sources which contain two private implementations of linked lists, Crystal::PointerLinkedList and Thread::LinkedList.

In order to help you further it’s essential that you explain what you’re even trying to do. How did you come up with this broken linked list implementation and why?

3 Likes
4

@Alain I see this question has also been cross-posted on Reddit - Dive into anything
When cross-posting please include links to the other locations.

5

I’ll do in the future.
The source of the code might come from gemini a.i. system.

2 Likes
6

I find such a shard, and it is still just working.
https://github.com/scriptnull/linkedlist.cr

7

I think there are small hints and lessons for the future on this page.

Soon, machines will be able to write better code than humans.
When that happens, people will not only have to ask for code fixes, but will also have to explain their goals, stories, and emotions in a straightforward manner.

This may be a very troublesome thing in some ways.