4

I'm trying to implement a delete() method to a list (no HEAD ref)

I find out that I can modify the parameter to a struct.

func (l *LinkedList) Delete(n *Node) {
    if n.next == nil {
        n = nil
    } else {
        current := &n
        *n = *n.next
        *current = nil
    }

}

The "else" part works fine, but deleting the last node does not modify the list

Tried using

*n = nil

But then I have the compile error.

cannot use nil as type Node in assignment

Code complete in this playground:

http://play.golang.org/p/Dhzyd7QHEw

2
  • Not sure if this is relevant or not, but have you looked at the built in list? golang.org/pkg/container/list
    – bojo
    Dec 30, 2013 at 6:48
  • Yes, this is more like how to implement a particular delete case. Thanks
    – Mariano DM
    Dec 30, 2013 at 22:09

1 Answer 1

5

You're just doing it wrong. I mean classic element removal from single linked list. Right way:

func (l *LinkedList) Delete(n *Node) {
    // if we want to delete the head element - just move the head pointer
    if l.head == n {
        l.head = n.next
        return
    }
    // otherwise find previous element to the one we are deleting
    current := l.head
    for current != nil && current.next != n {
        current = current.next
    }
    // and move that previous element next pointer to the next element
    if current != nil {
        current.next = n.next
    }
}

https://play.golang.org/p/_NlJw_fPWQD

So what was wrong in your example? In your Delete function you are receiving a pointer to some node. This pointer is local to your function, it's like a local variable. It doesn't matter if you assign nil to a local variable inside your function. Outside - no one will see such assignments. What you want to do - is to change the next pointer of the previous list item. This way the item will no longer be in the list. GC will remove the actual allocated memory.

UPDATE:

Since go pointers are "real" pointers, this can be implemented without special case for the head removal, by using an additional level of indirection, as suggested by Linus in his famous TED talk (and earlier in slashdot Q&A - see "favorite hack" question):

func (l *LinkedList) Delete(n *Node) {
    // initialize indirect with the address of a head pointer
    indirect := &(l.head)
    // until indirect has address of a pointer to the node we're deleting
    for *indirect != n {
        // check that it's not the end of the list
        if (*indirect).next == nil {
            // the node we're tryign to delete is not in the list
            return
        }
        // set indirect to the address of the next pointer
        indirect = &(*indirect).next
    }
    // indirect has address of a pointer we need to modify to delete the node
    *indirect = n.next
}

https://play.golang.org/p/hDy3hB5LUME

IMO two levels of inderection is harder to understand than a simple special case for deleting the head element, but Linus is not exactly an ordinary developer like myself :)

5
  • thanks for your answer Yes, Using the head is easy, part of the original question is how to do it if you only have a reference to the node to delete (No head) void delete_node(node* node) { node->Data = node->Next->Data; node* temp = node->Next->Next; delete(node->Next); node->Next = temp; } basically I'm trying to do this in go, in order to understand how pointers work. [link] stackoverflow.com/questions/9362896/…
    – Mariano DM
    Dec 30, 2013 at 22:03
  • @MarianoDM you can not do it with single linked list without head. The C code you wrote works only for the case when you are deleting non-last element.
    – Kluyg
    Dec 31, 2013 at 0:46
  • @Kluyg I think this does not work if you want to delete the head node
    – Sasan Rose
    Apr 11, 2018 at 12:24
  • @Kluyg So is there anyway to implement this as Linus suggested in golang? cdn-images-1.medium.com/max/800/1%2AGHFLYFB3vDQeakMyUGPglw.png
    – Sasan Rose
    Apr 11, 2018 at 20:49
  • 1
    @SasanRose Sure you can, go has real pointers, so here you go: play.golang.org/p/7lQMDjRoEjP IMO two levels of indirection is harder to understand than a simple special case for the head element, but Linus thinks otherwise :)
    – Kluyg
    Apr 12, 2018 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.