Home Tutorials Training Consulting Products Books Company Donate Contact us









NOW Hiring

Quick links

Share

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

3. Links and Literature

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