best way to handle list of integers and to - find, add, and delete

I need to create a list of integers and to be able to quickly add, delete, and find items in that list. While I could create a string containing them and a function to handle the add/delete/locate, it obviously makes more sense if Go can handle it for me. I looked at container/list and it appeared not entirely suitable, but maybe I'm wrong.

To very quickly implement something, I am using an integer array, however that is far from ideal, and I need to find a better solution. The list will probably hold up to 1,000 values.

Can someone please advise the "best" way to handle this in Go? An example is worth 1,000 words.

There is no 'best' way to your question as you don't state what you would like to do or what
sort of performance is important to you. The problem with data structures is, that every structure
performs better or worse depending on the circumstances. Generally I would say that an integer slice
would perform reasonably well for 1000 entries and is not so hard to use. Also the solution Nick
proposed is appealing, as it offers you O(1) lookup time (average!) for your values instead of
O(n) (unsorted) or O(log n) (sorted) search time in an array.

Go offers some operations to implement a []int store as you proposed:

• get: x[i]
• insert: x[i] = j or x = append(x, j) or use sorted insertion
• delete: x = append(x[:i], x[i+1:]...)
• search: in case you used sorted insertion, you can use sort.SearchInts, otherwise you need to loop and search linearly.

For more operations on slices see here.

The following example (playground) offers you a []int
with O(log n) time for searching and O(n) for insertion. Retrieval, deletion and setting
by index is, of course, O(1).

type Ints []int

// Insert v so that ints is sorted
func (ints *Ints) Append(v int) {
	i := sort.SearchInts(*ints, v)
	*ints = append((*ints)[:i], append([]int{v}, (*ints)[i:]...)...)
}

// Delete by index
func (ints *Ints) Delete(i int) {
	*ints = append((*ints)[:i], (*ints)[i+1:]...)
}

func (ints Ints) Search(v int) (int, bool) {
	i := sort.SearchInts(ints, v)
	return i, i < len(ints) && ints[i] == v
}

data := make(Ints, 0, 1000)
data.Append(100)
index,ok := data.Search(10)

As you can see in the example, Append searches for the place to insert the new value in, depending
on the size, effectively sorting the contents of the slice in ascending order. This makes it possible
to use binary search via sort.SearchInts, reducing the search time from O(n) to O(log n).
With that comes the cost to sort while inserting, which in turn is done by searching for a slot, which
costs O(log n) in worst case. Therefore, inserting is O(log n) as well.

In the interest of keeping it simple I would use a map. Maps are very fast, efficient and built in.

(playground link)

package main

import "fmt"

func main() {
	// Make our collection of integers
	xs := make(map[int]bool)

	// Add some things to the collection
	xs[1] = true
	xs[2] = true
	xs[3] = true

	// Find them
	if xs[2] {
		fmt.Println("Found 2")
	} else {
		fmt.Println("Didn't Find 2")
	}
	if xs[8] {
		fmt.Println("Found 8")
	} else {
		fmt.Println("Didn't Find 8")
	}

	// Delete them
	delete(xs, 2)

	// List them
	for x := range xs {
		fmt.Println("Contents", x)
	}
}

Which produces

<pre>
Found 2
Didn't Find 8
Contents 3
Contents 1
</pre>

Possibly the only disadvantage of this solution is that the integers aren't kept in any particular order, which may or may not be important to your application.

This is really more of an abstract data structure question. The answer depends on your use case. A slice of ints would do fine for the general case (look at append and such), but if you want finding items to be better than O(n) then you'll want them to be sorted, and insertion into a sorted int[] has a worst case of O(n) iirc.

So the question is which do you want to optimize, index, add, remove, or search?