How to remove an item from a linked list in Julia?

General Usage
1

Please help me how can we remove an item from a linked list.
In the code below, I can make a list by:

julia> L = list(1,3,5,7,9)
list(1,3,5,7,9)

Then, how to remove the 3rd element from L?

type Node
    value::Number
    next::Node

    function Node()
        n = new() # point to itself
        n.next = n
    end 

    function Node(value::Number, next::Node) # a regular constructor
        new(value, next)
    end 
end

#"Add Elements to List"
function unshift(head::Node, values::Number...)

    for v in reverse(values)
        head = Node(v, head)
    end 
    head
end 

function list(values::Number...)

    tail = Node()
    unshift(tail, values...)
end 

# Implement Iteration Interface
Base.start(head::Node) = head
Base.next(head::Node, n::Node) = n.value, n.next
Base.done(head::Node, n::Node) = n == n.next

# Using join for pretty printing:
function Base.show(io::IO, n::Node)
   println(io, "list(", join(n, ",")")" )
end 

# Add value to a linked list
function Base.append!(l::Node, x::Number...) 

    for v in reverse(x)
        l = Node(v, l)
    end 
    l
end
2

Is this a homework question?

3

I am major in geotechnical engineering and currently studying Julia for my research in graduate school. It’s not a homework for any class. I don’t know how to properly use pointers in this case. Please tell me how to do it

4

It’s a self-study problem, not a homework for a class. I am grateful if you can help me understand more

5

Alright, to remove e.g. the third node, traverse to the second node (using, for example, the iteration interface you defined). Store that node. Then traverse to the fourth node. Store that node. Then set the next field of the second node to the fourth node.

6

Thank you very much for your help! I got the result:


function Base.delete!(l::Node, index::Int64)

      l_before = l
      l_after = l
      for i = 1:(index-2)
            l_before = l_before.next
      end

      for i = 1:(index)
          l_after = l_after.next
      end
     
      l_before.next = l_after

      return l
end
7

Since you have defined an iteration interface, it might be good to use that instead of directly accessing the .next fields.

You could also do slightly better than now, by not restarting your iteration from 1 in the second loop. Instead, you could just keep going forward two steps from l_before.

8 
function Base.delete!(l::Node, index::Int64)

    l_before = l
    for i = 1:(index-2)
        l_before = l_before.next
    end
    l_before.next = l_before.next.next
    return l
end

Thank for your help! I understand your second idea and implemented it like the above. But how about the first idea? I dont know how to use that iteration interface as you mentioned

9

Something like

for (i,node) in enumerate(l)
  if i==index+1 
      lastnode.next=node.next
      break
  end
  lastnode=node
end

Though I don’t think that handles deleting at index=1.