Tutorial

Every programmer requires certain data structures for saving several elements. Usually every programming languages provides Arrays. These are fixed sized storage elements where every element can be addressed via an index.

The programmer usually requires a higher level of abstraction, e.g. Lists, Maps, Stacks, etc.

The Java programming language provides these elements very efficiently implemented in libraries. This article tries to describe how such elements could be implemented directly with Java constructs. The implementations in this articles are for demonstration and education purpose. They do not try to be as efficient as the standard libraries and they are not intended to be an replacement for the standard libraries.

The following example is contained in the project "de.vogella.datastructures.list".

A List represents a data structure which allows to dynamically add, acess and remove objects of the same type. Adding objects to the list is usually done via the method add(). The method get(int i) allows to retrieve the element at position i

			
package de.vogella.datastructures.list;

import java.util.Arrays;

public class MyList<E> {
	private int size = 0;
	private static final int DEFAULT_CAPACITY = 10;
	private Object elements[];
	
	public MyList() {
		elements = new Object[DEFAULT_CAPACITY];
	}

	public void add(E e) {
		if (size == elements.length) {
			ensureCapa();
		}
		elements[size++] = e;
	}
 

	private void ensureCapa() {
		int newSize = elements.length * 2;
		elements = Arrays.copyOf(elements, newSize);
	}

	@SuppressWarnings("unchecked")
	public E get(int i) {
		if (i>= elements.length) {
			throw new IndexOutOfBoundsException("Index: " + i + ", Size " + i );
		}
		return (E) elements[i];
	}
}

		

This is a small Junit test for the data structure. I use in the first test the MyList implementation and in the second test the standard Java List implementation.

			
package de.vogella.datastructures.list;
import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

import static org.junit.Assert.assertTrue;

public class MyListTest {


	@Test(expected=IndexOutOfBoundsException.class)
	public void testMyList() {
		MyList<Integer> list = new MyList<Integer>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(3);
		list.add(4);
		assertTrue(4 == list.get(4));
		assertTrue(2 == list.get(1));
		assertTrue(3 == list.get(2));
		
		list.get(100);
	}

	@Test(expected=IndexOutOfBoundsException.class)
	public void testList() {
		List<Integer> list = new ArrayList<Integer>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(3);
		list.add(4);
		assertTrue(4 == list.get(4));
		assertTrue(2 == list.get(1));
		assertTrue(3 == list.get(2));
		
		list.get(100);
	}
	
	
	
}

		

The following example is contained in the project "de.vogella.datastructures.map".

A map represents a data structure in which collections of unique key and collections of values are stored where each key is associated with one value. The operation of finding the value is called lookup.

A standard array is a special case of a map where the key are the index number of the elements pointing to the object in the array.

The standard Java interfaces for maps is import java.util.Map. Standard implementations of Maps are for example java.util.HashMap or import java.util.concurrent.ConcurrentHashMap

A simple map with the option to add, get, remove and get the size of the Map could be implemented like the following. Please note that this map is not very fast for large sets.

This would be an entry.

			
package de.vogella.datastructures.map;

public class MyEntry<K, V> {
	private final K key;
	private V value;

	public MyEntry(K key, V value) {
		this.key = key;
		this.value = value;
	}

	public K getKey() {
		return key;
	}

	public V getValue() {
		return value;
	}

	public void setValue(V value) {
		this.value = value;
	}
}

		

This is the map implementation based on MyEntry.

			
package de.vogella.datastructures.map;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class MyMap<K, V> {
	private int size;
	private int DEFAULT_CAPACITY = 16;
	@SuppressWarnings("unchecked")
	private MyEntry<K, V>[] values = new MyEntry[DEFAULT_CAPACITY];


	public V get(K key) {
		for (int i = 0; i < size; i++) {
			if (values[i] != null) {
				if (values[i].getKey().equals(key)) {
					return values[i].getValue();
				}
			}
		}
		return null;
	}

	public void put(K key, V value) {
		boolean insert = true;
		for (int i = 0; i < size; i++) {
			if (values[i].getKey().equals(key)) {
				values[i].setValue(value);
				insert = false;
			}
		}
		if (insert) {
			ensureCapa();
			values[size++] = new MyEntry<K, V>(key, value);
		}
	}

	private void ensureCapa() {
		if (size == values.length) {
			int newSize = values.length * 2;
			values = Arrays.copyOf(values, newSize);
		}
	}

	public int size() {
		return size;
	}

	public void remove(K key) {
		for (int i = 0; i < size; i++) {
			if (values[i].getKey().equals(key)) {
				values[i] = null;
				size--;
				condenseArray(i);
			}
		}
	}

	private void condenseArray(int start) {
		for (int i = start; i < size; i++) {
			values[i] = values[i + 1];
		}
	}

	public Set<K> keySet() {
		Set<K> set = new HashSet<K>();
		for (int i = 0; i < size; i++) {
			set.add(values[i].getKey());
		}
		return set;
	}
}

		

And a small test.

			
package de.vogella.datastructures.map;

import static org.junit.Assert.assertEquals;

import java.util.HashMap;
import java.util.Map;

import org.junit.Before;
import org.junit.Test;

public class MyMapTest {

	@Before
	public void setUp() throws Exception {
	}

	@Test
	public void testStandardMap() {
		// Standard Map
		Map<String, Integer> map = new HashMap<String, Integer>();
		map.put("Lars", 1);
		map.put("Lars", 2);
		map.put("Lars", 1);
		assertEquals(map.get("Lars"), 1);

		for (int i = 0; i < 100; i++) {
			map.put(String.valueOf(i), i);
		}
		assertEquals(map.size(), 101);

		assertEquals(map.get("51"), 51);
		map.keySet();
	}

	@Test
	public void testMapMap() {

		// MyMap
		MyMap<String, Integer> map = new MyMap<String, Integer>();
		map.put("Lars", 1);
		map.put("Lars", 2);
		map.put("Lars", 1);
		assertEquals(map.get("Lars"), 1);
		for (int i = 0; i < 100; i++) {
			map.put(String.valueOf(i), i);
		}
		assertEquals(map.size(), 101);
		assertEquals(map.get("51"), 51);

	}
}

		

The following example is contain in the project "de.vogella.datastructures.stack".

The stack offers to put new object on the stack ( method push()) and to get objects from the stack (method pop()). A stack returns the object according to last-in-first-out (LIFO), e.g. the object which was placed latest on the stack is returned first. Java provides a standard implementation of a stack in java.util.Stack.

The following are two implementations of stacks, one based on arrays the other based on ArrayLists.

			
package de.vogella.datastructures.stack;

import java.util.Arrays;

public class MyStackArray<E> {
	private int size = 0;
	private static final int DEFAULT_CAPACITY = 10;
	private Object elements[];

	public MyStackArray() {
		elements = new Object[DEFAULT_CAPACITY];
	}

	public void push(E e) {
		if (size == elements.length) {
			ensureCapa();
		}
		elements[size++] = e;
	}

	@SuppressWarnings("unchecked")
	public E pop() {
		E e = (E) elements[--size];
		elements[size] = null;
		return e;
	}

	private void ensureCapa() {
		int newSize = elements.length * 2;
		elements = Arrays.copyOf(elements, newSize);
	}
}

		

			
package de.vogella.datastructures.stack;

import java.util.ArrayList;

public class MyStackList<E> extends ArrayList<E> {

	private static final long serialVersionUID = 1L;

	public E pop() {
		E e = get(size() - 1);
		remove(size() - 1);
		return e;
	}

	public void push(E e) {
		add(e);
	}

}

		

This is a small JUnit test for the data structure.

			
package de.vogella.datastructures.stack;

import static org.junit.Assert.assertTrue;

import org.junit.Before;
import org.junit.Test;

public class MyStackTest {

	@Before
	public void setUp() throws Exception {

	}

	@Test
	public void testStackArray() {
		MyStackArray<Integer> stack = new MyStackArray<Integer>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(3);
		stack.push(4);
		assertTrue(4 == stack.pop());
		assertTrue(3 == stack.pop());
		assertTrue(3 == stack.pop());
		assertTrue(2 == stack.pop());
		assertTrue(1 == stack.pop());
	}

	@Test
	public void testStackList() {
		MyStackList<Integer> stack = new MyStackList<Integer>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(3);
		stack.push(4);
		assertTrue(4 == stack.pop());
		assertTrue(3 == stack.pop());
		assertTrue(3 == stack.pop());
		assertTrue(2 == stack.pop());
		assertTrue(1 == stack.pop());
	}

}

		

Please help me to support this article:

Before posting questions, please see the vogella FAQ. If you have questions or find an error in this article please use the www.vogella.de Google Group. I have created a short list how to create good questions which might also help you.

http://www.cs.princeton.edu/introcs/home/ Java Book about Algorithms and Data Structures