An Array of Linear list in java

Posted By: Java Examples - 8:48 PM

Share

& Comment

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.

Java version of the  Array of linked /Linear  list   is given below : 

/** array implementation of LinearList */
package dataStructures;

import javax.swing.JOptionPane;

//import utilities.*;     // has array resizing class

public class ArrayLinearList implements LinearList {
 // 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 ArrayLinearList(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 ArrayLinearList() {
  // 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[]) {
  ArrayLinearList markList = new ArrayLinearList(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));

  JOptionPane.showMessageDialog(null, markList.toString(),
    "List of Marks", 1);
 }
}

Output of this program is given bellow :

About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .