Support free tutorials









vogella training Training Books



How to implement common datastructures (List, Stack, Map) in plain Java - Tutorial

Lars Vogel

Version 1.1

09.10.2012

List, Map and Stack implementations in Java

This article describes how to implement data structures (List Stack, Map) in Java.

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.


Table of Contents

1. Datastructures
2. List
3. Map - Associative array
4. Stack
5. Support this website
5.1. Thank you
5.2. Questions and Discussion
6. Links and Literature

1. Datastructures

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.

2. List

See Implementing a List data structure in Java.

3. Map - Associative array

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);

  }
} 

4. Stack

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());
  }

} 

5. Support this website

This tutorial is Open Content under the CC BY-NC-SA 3.0 DE license. Source code in this tutorial is distributed under the Eclipse Public License. See the vogella License page for details on the terms of reuse.

Writing and updating these tutorials is a lot of work. If this free community service was helpful, you can support the cause by giving a tip as well as reporting typos and factual errors.

5.1. Thank you

Please consider a contribution if this article helped you. It will help to maintain our content and our Open Source activities.

5.2. Questions and Discussion

If you find errors in this tutorial, please notify me (see the top of the page). Please note that due to the high volume of feedback I receive, I cannot answer questions to your implementation. Ensure you have read the vogella FAQ as I don't respond to questions already answered there.

6. Links and Literature

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