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

Posted: December 24, 2012 in Java Posts
Tags: , , , , , , , , , , , ,

English: Diagram of a real life implementation...

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.


ProbioticSmart.com Online Store
Table of Contents

1. Datastructures
2. List
3. Map – Associative array
4. Stack
5. Thank you
6. Questions and Discussion
7. 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

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

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

package de.vogella.datastructures.list;

import java.util.Arrays;

public class MyList {
  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>= size || i <0) {
      throw new IndexOutOfBoundsException("Index: " + i + ", Size " + i);
    }
    return (E) elements[i];
  }
}

The following show contains 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 list = new MyList();
    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(6);
  }

  @Test(expected=IndexOutOfBoundsException.class)
  public void testNegative() {
    MyList list = new MyList();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(3);
    list.add(4);
    list.get(-1);
  }

  @Test(expected=IndexOutOfBoundsException.class)
  public void testList() {
    List list = new ArrayList();
    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(6);
  }

}

Tip

You typically also have the remove(int i) method to remove the element at position i but I leave this implementation for the reader. To delete elements in your list just shift all elements after position i one position to the left and decrease size.

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 keySet() {
    Set set = new HashSet();
    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 {
  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 extends ArrayList {

  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 stack = new MyStackArray();
    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 stack = new MyStackList();
    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. Thank you

 

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s