Problem with Linked List

Getting Help Code Review
1

Hello! I’m trying to build an app based on Aho/Ullmann’s linked list model from “Foundation of Computer Science in C”, they does use a struct with a pointer type to it like this

type Node struct {
    label string
    next *Node
}

type List *Node

So, while the operation to insert new nodes does the job, I’m experiencing some technical difficulties by deleting Node from the list. I can not find a solution to my problem: the program fails with panic when the delete method reaches the end of the linked list without find the data element. Here is the code

func (l *Node) delete(data string) {
   if l != nil {
       if l.label == data {
          *l = *l.next
       } else {
           l = l.next
           l.delete(data)
       }
}

Your support is greatly appreciated

2

You need to stop when next is the empty list.

3

Hi Nobbz, thank you for your reply. If I add else if branch

  if l != nil {
       if l.next == nil && l.label == data {
           l = nil
       } else if l.label == data {
          *l = *l.next
       } else {
           l = l.next
           l.delete(data)
       }
}

then the method doesn’t work, the last element is not deleted when data=label, why?

4

Try this small example to figure out how to insert and delete from a simple linked list. The code is C like but also Go idiomatic. I put comments in some points, pay attention of them.

https://play.golang.org/p/85WH544lx44

LE: Working with data structures and algorithms often need drawing the structures and pointers on a piece of paper. Try this to better understand the pointers and their movement.

1 Like
5

Hi George, I’m trying to solve the problem with recursion because I’m carrying out the exercises from Aho/Ullman’s book “Foundation of Computer Science in C”, chapter six, “List data model”. Then I’d like to use methods instead of functions. So here the last version of delete method

func (l *List) delete(data string, prev *Node) {
if l != nil {
    // It's Head
    if prev == nil && l.label == data
        // remove the head: I don't know how to accomplish this
       return
    }
    // It's Last element
    if l.next == nil && l.label == data {
       // No problem with this block of code
       prev.prossimo = nil 
       return
    }
    // It's Tail
    if l.next == data {
        // No problem with this block of code
         *l = *l.next
         return
    }   
    p := l
    l = l.next
    l.delete(data, p)
}
}

I added a second parameter, the pointer to the previous node, but now I can not erase the head when the list contains only one element.

6

The go compiler does not perform tail call optimisations, therefore any recursive solution will blow up your stack on long enough lists.

It will be much simpler to use a for and more reliable.

7

I’n not so sure about what you want to do, a singly linked list or a doubly linked list?
:confused:

8

Singly linked list. I have to solve the same problem as this user has but the algorithm must be recursive and the method’s parameter is the element to delete not a node to it.

9

I know but it’s an exercise. Thank you for the advice.

10

OK so here I came up with this solution.

  1. Setup the linked list
dictionary = new(Node)
  1. Add a word
dictionary.add(input)
...
func (l *Node) add(data string) {
    if l != nil {

        n := &Node{data, l.next}
        l.next = n
    }
}
  1. Delete a word
dictionary.delete(input, nil)
...
func (l *Node) delete(data string, prev *Node) {

	if l != nil {
		// It's Head
		if prev == nil && l.label == data {
			return
		}
		// It's Last element
		if l.next == nil && l.label == data {
			prev.next = nil
			return
		}
		// It's Tail
		if l.label == data {
			*l = *l.next
			return
		}

		p := l
                l = l.next
		l.delete(data, p)

	}

}

I did note that the Head can not be zeroed with nil (strange to say) so if the first condition is true the procedure returns without doing anything.