Data structure optimized for adding items (at end of list), iterating, and removing items

Question

I need a data structure which will support the following operations in a performant manner:

• Adding an item to the end of the list
• Iterating through the list in the order the items were added to it (random access is not important)
• Removing an item from the list

What type of data structure should I use? (I will post what I am currently thinking of as an answer below.)

Answer 1

You should use a linked list. Adding an item to the end of the list is O(1). Iterating is easy, and you can remove an item from any known position in the list in O(1) as well.

Answer 2

I am thinking of using a simple list of the items. When a new item is added I will just add it to the end of the list. To remove an item, I won't actually remove it from the list, I will just mark it as deleted, and skip over it when iterating through the items.

I will keep track of the number of deleted items in the list, and when more than half of the items are deleted, I will create a new list without the deleted items.

Answer 3

Circular & Doubly-Linked List. It satisfies all 3 requirements:

Adding an item to the end of the list: O(1). By add to Head->prev. It supports Iterating through the list in the same order in which they were added. You can remove any element.

Answer 4

It sounds like a linked list, however there's a catch you need to consider. When you say "removing an item from the list", it depends on whether you have the "complete item" to remove, or just its value.

I will clarify: let's say your values are strings. You can construct a class/struct containing a string and two linking pointers (forwards and backwards). When given such a class, it's very easy to remove it from the list in O(1). In pseudo code, removing item c looks like this (please disregard validation tests):

c.backwards = c.forwards
if c.backwards = null: head = c.forwards
if c.forwards = null: tail = c.backwards
delete c

However, if you wish to delete the item containing the string "hello", that would take O(n) because you would need to iterate through the list.

If that's the case I would recommend using a combination of a linked list and and hash table for O(1) lookup. Inserting to the end of the list (pseudo code):

new_item = new Item(value = some_string, backwards = tail, forwards = null)
tail.forwards = new_item
tail = new_item
hash.add(key = some_string, value = new_item)

Scanning through the list is just scanning through the linked list, no problems:

i = head

while i != null:
    ... do something with i.value ...
    i = i.forwards

Removing an item from the list by value (pseudo code, no validation testing):

item_to_remove = hash.find_by_key(some_string)
if (item_to_remove != null):
    hash.delete_key(some_string)
    item_to_remove.backwards = item_to_remove.forwards
    if item_to_remove.forwards = null: tail = item_to_remove.backwards
    if item_to_remove.backwards = null: head = item_to_remove.forwards
    delete item_to_remove

Answer 5

Assuming Java (other languages have similar structures, but I found the JavaDocs first):

• ArrayList if you have the index of the item you want to delete
• LinkedHashMap if you only have the item and not its position