Implementing Linked List in Java using Array

In this program, you'll learn to implement Linked List in Java using Array Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including stacks, queues, associative arrays, andsymbolic expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.

The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.

On the other hand, simple linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list (assuming that the last node is not maintained as separate node reference in the list structure), or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require scanning most or all of the list elements.

Operations :

1. isEmpty() - Returns true if the List is empty ,false other wise.
2. size() - Give the number of element in the list.
3. get(theIndex) - Give the element with gives index.
4. indexOf(theElement) - Determines the index of a given element.
5. remove(theIndex) - Removes element with a given index and returns it.add(theIndex,theElement) - Add a given element so that new element has a specified index.

Linear list Interface:

	public interface LinkedList {
	public boolean isEmpty();
	public int size();
	public Object get(int index);
	public int indexOf(Object elem);
	public Object remove(int index);
	public void add(int index, Object obj);
	public String toString();
	}

view raw LinkedList.java hosted with ❤ by GitHub

Implementing Linked List in Java using Array

	public class ArrayLinkedList implements LinkedList {
	// data members
	protected Object[] element; // array of elements
	protected int size; // number of elements in array
	/**
	* create a list with initial capacity initialCapacity
	*
	* @throws IllegalArgumentException when initialCapacity < 1
	*/
	public ArrayLinkedList(int initialCapacity) {
	if (initialCapacity < 1)
	throw new IllegalArgumentException("initialCapacity must be >= 1");
	// size has the default initial value of 0
	element = new Object[initialCapacity];
	size = 0;
	}
	/**
	* create a list with initial capacity 10
	*/
	public ArrayLinkedList() {
	// use default capacity of 10
	this(10);
	}
	/**
	* @return true if list is empty
	*/
	public boolean isEmpty() {
	return size == 0;
	}
	/**
	* @return current number of elements in list
	*/
	public int size() {
	return size;
	}
	/**
	* @return element with specified index
	* @throws IndexOutOfBoundsException when index is not between 0 and size - 1
	*/
	public Object get(int index) {
	checkIndex(index);
	return element[index];
	}
	/**
	* @throws IndexOutOfBoundsException when index is not between 0 and size - 1
	*/
	void checkIndex(int index) {
	if (index < 0 || index >= size)
	throw new IndexOutOfBoundsException("index = " + index
	+ " size = " + size);
	}
	/**
	* @return index of first occurrence of theElement, return -1 if theElement
	* not in list
	*/
	public int indexOf(Object theElement) {
	// search element[] for theElement
	for (int i = 0; i < size; i++)
	if (element[i].equals(theElement))
	return i;
	// theElement not found
	return -1;
	}
	public Object remove(int index) {
	checkIndex(index);
	// valid index, shift elements with higher index
	Object removedElement = element[index];
	for (int i = index + 1; i < size; i++)
	element[i - 1] = element[i];
	element[--size] = null; // enable garbage collection
	return removedElement;
	}
	public void add(int index, Object theElement) {
	if (index < 0 || index > size)
	// invalid list position
	throw new IndexOutOfBoundsException("index = " + index
	+ " size = " + size);
	// valid index, make sure we have space
	if (size == element.length)
	// no space, double capacity
	// element = ChangeArrayLength.changeLength1D(element, 2 *size);
	// -- you define this class ChagedArrayLength in a package utilities and
	// import the package.
	{
	Object tempEl[] = new Object[2 * size];
	System.arraycopy(element, 0, tempEl, 0, size);
	element = tempEl;
	}
	// shift elements right one position
	/*
	* for (int i = size - 1; i >= index; i--) element[i + 1] = element[i];
	* this effect can be done using System.arrayCopy as follows
	*/
	System.arraycopy(element, index, element, index + 1, size - index);
	element[index] = theElement;
	size++;
	}
	public String toString() {
	StringBuffer s = new StringBuffer("[");
	// put elements into the buffer
	for (int i = 0; i < size; i++)
	if (element[i] == null)
	s.append("null, ");
	else
	s.append(element[i].toString() + ", ");
	if (size > 0)
	s.delete(s.length() - 2, s.length());
	// remove last ", "
	s.append("]");
	// create equivalent String
	return new String(s);
	}
	public static void main(String args[]) {
	ArrayLinkedList markList = new ArrayLinkedList(10);
	markList.add(0, new Integer(60));
	markList.add(1, new Integer(70));
	markList.add(2, new Integer(75));
	markList.add(0, new Integer(58));
	markList.add(2, new Integer(72));
	markList.add(2, new Integer(56));
	System.out.println(markList.toString());
	}
	}

view raw ArrayLinkedList.java hosted with ❤ by GitHub

When you run the program, the output will be:

[58, 60, 72, 70, 75]