NOW Hiring

Quick links

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.

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

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. About this website

6. Links and Literature

6.1. vogella GmbH training and consulting support

TRAINING SERVICE & SUPPORT

The vogella company provides comprehensive training and education services from experts in the areas of Eclipse RCP, Android, Git, Java, Gradle and Spring. We offer both public and inhouse training. Whichever course you decide to take, you are guaranteed to experience what many before you refer to as “The best IT class I have ever attended”.

The vogella company offers expert consulting services, development support and coaching. Our customers range from Fortune 100 corporations to individual developers.

Copyright © 2012-2016 vogella GmbH. Free use of the software examples is granted under the terms of the EPL License. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.

See Licence.