ArrayLists

Array-based list data structure.

Java

Built-in ArrayList type

Java Collections uses built-in array-based list structure, ArrayList<>. Link: https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html

Bringing the Python List to Java

Here is an implementation of a Python list in Java, which is pretty close in style to the Python list, which works transparently with any data so long as they have matching types.

https://git.charlesreid1.com/cs/java/src/master/arrays/python-list/PythonList.java

public class PythonList { 

	public static void main(String[] args) { 

		PythonList p = new PythonList();
		Random r = new Random();

		int n = 50;

		for(int i=0; i<100; i++ ) {
			p.append(r.nextInt(6)+1);
			System.out.println(p);
		}
		System.out.println(p);
	}


        ///////////////////////////////////////////////////


	final private int INITCAP = 10;
	private Object[] data;
	public int length;

	public PythonList() {
		length = 0;
		data = new Object[INITCAP];
	}

	public Object get(int ix) {
		return data[ix];
	}

	public void append(Object o) { 
		if(data.length==length) {
		    resize(data.length*2);
		}
		data[length] = o;
		length++;
	}

	public void remove(int rmi) { 
		if(rmi>=length) { 
			throw new ArrayIndexOutOfBoundsException("Error accessing index "+rmi);
		}
		data[rmi] = null;
		for(int i=rmi; i<length; i++) {
			data[i] = data[i+1];
		}
		length--;
		if(length<(data.length/4)) {
			resize(data.length/2);
		}
	}

	private void resize(int newcap) {
		Object[] newarr = new Object[newcap];
		for(int i=0; i<length; i++ ) { 
			newarr[i] = data[i];
		}
		data = newarr;
	}

	public String toString() {
		return Arrays.toString(data);
	}
}

Python

The essence of this class is that it is a dynamically sizable, array-based structure. In the Goodrich Python book, the array-based list, emulating the built-in Python list type, is covered in Chapter 3 - the first data structure you learn about in Python is a list. It's a wonderfully simple data container. The Java version of Goodrich doesn't get around to implementing your own array-based list type until Chapter 6!

Here is an implementation of a few of the concepts from Chapter 3 in the form of the DynamicArray class, which emulates the built-in, array-based list type in its simple design: https://git.charlesreid1.com/cs/python/src/master/arrays/DynamicArray.py

This implementation uses the ctype module to access a low-level array of Python Objects.

import ctypes

class DynamicArray:
    """
    A dynamic array class that works like a list.
    """

    .........snip............


    def _resize(self,c):
        """ Resize to capacity c (private)"""
        print("Resizing array: {0:4d} elements, {1:5d} capacity".format(self._n,c))
        B = self._make_array(c) # bigger array
        for k in range(self._n):
            B[k] = self._A[k] # copy existing elements only
        self._A = B # forget the old array
        self._capacity = c # update capacity

    def _make_array(self,n):
        """Make the internal array (private)"""
        return (n*ctypes.py_object)()