title: Implementing data structures in golang
body: <p>So I have to implement some data structures in a language compiled to native-code. I did that in C++, but now I wanted to try another language, that I didn't worked with before. I chose <code>golang</code>. First data structure would be an array (capable of dynamic append, removal, etc.) In C++ I got something like this:</p>
  
  <pre><code>class array{
      int n;
      int *t;
      .
      .
      .
  }
  </code></pre>
  
  <p>So <code>n</code> is the number of elements and <code>*t</code> is a pointer to an array, which would be created in a constructor. I wrote <code>append</code>, <code>pop_back</code>, <code>remove</code>, <code>find</code> methods and so on. Now when I switch to golang, my first attempt was to create a <code>struct</code> something like this:</p>
  
  <pre><code>type array struct {
      n int
      ...
  }
  </code></pre>
  
  <p>and well I didn't know what should be here instead of dots. So I did some reading (got Brian W. Kernighan book) and I found about 2 data types : <code>arrays</code> and <code>slices</code>. I found a piece of code for appending to the array (take an array, resize it (n+1) and insert a value). I tested it, works (I tested it on a built-in <code>slice</code> type). Now when I would have my own array type I don't know if I should use <code>slice</code>, or maybe something else. I have this piece of code, which would measure the times for <code>Append()</code> operation, depending on the number of elements:</p>
  
  <pre><code>package main
  
  import (
      "fmt"
      "time"
  )
  
  type array struct {
      n int
  }
  func Append(slice []int, element int) []int {
      n := len(slice)
      total := len(slice) + 1
      if total &gt; cap(slice) {
          // Reallocate. Grow to 1.5 times the new size, so we can still grow.
          newSize := total*3/2 + 1
          newSlice := make([]int, total, newSize)
          copy(newSlice, slice)
          slice = newSlice
      }
      slice = slice[:total]
      slice[n] = element
      return slice
  }
  
  func main() {
      var seconds int64 = 0
      sizes := [5]int64{1000, 5000, 10000, 50000, 100000}
      for i := 0; i &lt; 5; i++ {
          var j int64
          for j = 0; j &lt; 100; j++ {
              array := make([]int, sizes[i], sizes[i]+1)
              start := time.Now()
              array = Append(array, 1)
              elapsed := time.Since(start)
              seconds += int64(elapsed)
          }
          seconds = seconds/100
          fmt.Println(seconds)
          seconds = 0
      }
      fmt.Println("The end")
  }
  </code></pre>
  
  <p>I always do <code>array := make([]int, sizes[i], sizes[i]+1)</code> cuz I don't want to make capacity changing and copying be relevant here. As far as I know there should be no difference if array has 1000 elements or 100000 - the time should be approximately the same, but the results I've got are different : </p>
  
  <pre><code>1810
  1589
  46
  99
  244
  The end
  </code></pre>
  
  <p>The times differ. Now my questions are:</p>
  
  <ol>
  <li>What basic type should I use in my own array type?</li>
  <li>Can I somehow reallocate the memory (increment/decrement the length) without operating on capacity?</li>
  <li>Is there a way to change this algorithm to make its computional complexity <code>O(1)</code>, so it doesn't matter how many arguments are there?</li>
  </ol>