How to implement common ADTs given of the language

abstract_data_types.md

List

Java

ArrayList vs LinkedList vs Vector

We should always use ArrayList when we need a List, except for a few use cases where LinkedList is more adapted (when implementing a queue for example). We should also avoid using Vector which is a legacy class. If we need synchronisation, we will use the Collections.synchronizedList wrapper.

Method	ArrayList	LinkdedList
get(int i)	O(1)	O(n/4)
add(E e)	O(1), O(n) worst-case	O(1)
add(int i, E e)	O(n/2)	O(n/4), O(1) best-case
remove(int i)	O(n/2)	O(n/4)
Iterator.remove()	O(n/2)	O(1)
ListIterator.add(E e)	O(n/2), O(1) bc, O(n) wc	O(1)
Memory	efficient usage of memory	more overhead because each element stores 2 pointers
Performance	efficient because using contiguous memory	bad real-world performances because it's slower to deal with a lot of small memory objects
Implementation	Array	Doubly Linked List
Resizing factor	50%	0%

Usage

import java.util.List;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
		List<Integer> l = new ArrayList<Integer>();
		l.add(1);    // [1]
		l.add(0, 2); // [2, 1]
		l.add(1, 3); // [2, 3, 1]
		l.remove(0); // [3, 1]
		System.out.println(l);
        }
}

Go

container/list vs slice

Most of the time a slice will do fine.

Usage

• Doubly Linked List

package main

import (
	"container/list"
)

func main() {
	l := list.New()
	l.PushBack(1)               // [1]
	l.PushFront(2)              // [2, 1]
	l.InsertBefore(3, l.Back()) // [2, 3, 1]
	l.Remove(l.Front())         // [3, 1]
	for e := l.Front(); e != nil; e = e.Next() {
		println(e.Value.(int))
	}
}

• Slice

package main

func main() {
	l := []int{}
	l = append(l, 1)                         // [1]
	l = append([]int{2}, l...)               // [2, 1]
	l = append(l[:len(l)-1], 3, l[len(l)-1]) // [2, 3, 1]
	l = l[1:]                                // [3, 1]
	for i := range l {
		println(l[i])
	}
}

Map

Java

HashMap, LinkedHashMap, TreeMap and Hashtable

• HashMap: Efficient map implemented with bucket hashing. You should always use it if you don't need ordering when retrieving the keys.
• LinkedHashMap: The buckets are doubly linked to enable to retrieve the keys in the order they were inserted.
• TreeMap: Map performing O(log(n)) operations, because it is implemented via a red-black tree. However it can be useful when we need to retrieve the keys in sorted order.
• Hashtable: Deprecated. It is synchronized and doesn't allow null keys/values.

Note: From Java 8, HashMap uses a balanced tree instead of a linked list to deal with hash collisions.

Usage

import java.util.*;

public class Main {
        public static void main(String[] args) {
                Map<String, Integer> m = new HashMap<String, Integer>();
                m.put("1", 1); // {1=1}
                m.put("2", 2); // {1=1, 2=2}
                m.remove("1"); // {2=2}
                System.out.println(m);
        }
}