Home Tutorials Training Consulting Products Books Company Donate Contact us









Online training

Events

Quick links

Share

Lars Vogel (c) 2008, 2016 vogella GmbH Version 1.2, 29.09.2016

List implementations in Java. This article describes how to implement a list data structure 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 Java libraries structures.

1. 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<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>= 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<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(6);
    }


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



}
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.

2. Links and Literature

3. vogella training and consulting support

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