Have Geek Brain

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

I need a data structure that will support the following operations at runtime:

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

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

+1


a source to share


5 answers


You must use a linked list. Adding an item to the end of the list is O (1). Iteration is simple and you can remove an item from any known position in the list in O (1).



+3


a source


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

I'll clarify: let your values ​​be strings. You can build a class / struct containing a string and two binding pointers (forward and backward). When given a class like this, it is very easy to remove it from the list in O (1). In pseudocode, removing the c element looks like this (please ignore the checks):

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

However, if you want to remove an element containing the string "hello", it will take O (n), because you will have to iterate over the list.

If in this case, I would recommend using a combination of linked list and hash table for O (1) lookups. Insert at the end of the list (pseudocode):



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)

List crawling is just viewing a linked list, no problem:

i = head

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

Removing an item from a list by value (pseudocode, no validation check):

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
+2


a source


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

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

0


a source


Round and doubly linked list. It meets all three requirements:

Adding an item to the end of the list: O (1). Add to Head-> prev. It keeps iterating through the list in the same order in which they were added. You can remove any item.

0


a source


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

  • ArrayList if you have the index of the element you want to remove.
  • LinkedHashMap if you only have an item and not its position
0


a source






More articles:


All Articles