Linked list that support modifications during iteration

Question

Update:

Fixed last item is not removed during iteration
Fixed clear() during iteration does nothing
Fixed addition of removed item is ignored

The lasted code can be found here. Unitest can be found here.

As part of my Signals library, I needed to create a custom Linked List with the below properties

It should allow "addition" and "removal" of items during iteration, aka when iterator() is called, like in the for loop.
It should ignore-Addition of duplicated items.
It should ignore-Removal of nonexisting items.
it should be a thread-safe

I ended up with the below implementation. Please tell me what do you think in terms of

clean code
bugs
performance

package com.gazman.signals

import java.util.*

internal class ListenersList<T> : Iterable<T?> {
    private val none = Node<T>(null)
    private var head: Node<T>? = null
    private var tail: Node<T>? = null
    private var map = IdentityHashMap<T, Node<T>>()

    fun isNotEmpty(): Boolean {
        return map.isNotEmpty()
    }

    fun add(listener: T) {
        synchronized(this) {
            if (map.containsKey(listener)) {
                return
            }
            val node = Node(listener)
            map[listener] = node

            if (tail == null) {
                head = node
                tail = node
            } else {
                node.previous = tail
                tail?.next = node
                tail = node
            }
        }
    }

    fun remove(listener: T) {
        synchronized(this) {
            val node = map[listener]
            node?.previous?.next = node?.next
            node?.next?.previous = node?.previous
        }
    }

    override fun iterator(): Iterator<T?> {
        return object : Iterator<T?> {
            var node: Node<T>? = none

            override fun hasNext() = node != null && node != tail

            override fun next(): T? {
                node = if (node == none) {
                    [email protected]
                } else {
                    node?.next
                }
                return node?.value
            }

        }
    }

    fun clear() {
        synchronized(this) {
            head = null
            tail = null
            map.clear()
        }
    }
}

Node

package com.gazman.signals

internal class Node<T>(val value: T?) {
    var previous: Node<T>? = null
    var next: Node<T>? = null
}

forsvarir · Accepted Answer · 2021-03-23 22:51:18Z

I haven't done much Kotlin, however something looked wrong and I was curious, so I wrote some tests. I had a couple of failures, so you may have issues, or it may be that I'm expecting the wrong behaviour. There's three scenarios to consider. I've defined a list of string to make it easy to test.

val list = ListenersList<String>()

clear

You've said that you want the code to be tolerant of adding/removing items during iteration. I assumed that it would therefor also be tolerant of clear being called (it seems equivalent to calling remove on every item). So, I would expect it to iterate up to the point of the clear being called. This isn't what happens. Instead, it iterates past the end of the list. So, for example:

@Test
fun clearMiddleWorks() {
    list.add("a")
    list.add("b")
    list.add("c")

    var items = ""

    for (item in list) {
        if(item == "a")
            list.clear()
        items += item
    }

    assertEquals("a", items)
}

This test fails, because instead of exiting the loop after "a", it continues building up the string, and fails on "a" != "abcnull"

end removal

This issue exists in the code you've posted, however it looks like you've cleaned it up in your latest github version. Removing the last item in the list during iteration, fails to terminate as expected:

@Test
fun removalOfEndWorks() {
    list.add("a")
    list.add("b")
    list.add("c")

    var items = ""

    for (item in list) {
        if(item == "b") {
            list.remove("c")
        }
        items += item
    }

    assertEquals("ab", items)
}

This fails with "ab" != "abnull"

remove and add conflict

This may actually be expected behaviour, however it seems odd to me. If I remove an item from the list, whilst I'm iterating over it, then add an item with the same value, I'd expect that item to be treated the same was as if I'd added a new item, however it isn't. So, this test passes:

@Test
fun removalAdditionOtherInMiddleWorks() {
    list.add("a")
    list.add("b")
    list.add("c")

    var items = ""


    for (item in list) {
        if(item == "a") {
            list.remove("b")
            list.add("d")
        }
        items += item
    }

    assertEquals("acd", items)
}

And this test fails:

@Test
fun removalAdditionOfMiddleWorks() {
    list.add("a")
    list.add("b")
    list.add("c")

    var items = ""


    for (item in list) {
        if(item == "a") {
            list.remove("b")
            list.add("b")
        }
        items += item
    }

    assertEquals("acb", items)
}

It fails because the added in "b" is ignored, so "acb" != "ac". Is this expected?

Thank you! This is an awesome code review. I now updated the question with a list of bugs I fixed and links for the up to date code — Ilya Gazman
– Ilya Gazman, Commented Mar 24, 2021 at 14:10

Stack Exchange Network

Linked list that support modifications during iteration

1 Answer 1

clear

end removal

remove and add conflict

You must log in to answer this question.

Hot Network Questions

Linked list that support modifications during iteration

1 Answer 1

clear

end removal

remove and add conflict

You must log in to answer this question.

Related

Hot Network Questions