[Go to site: main page, start]
Scribd
Upload
59 views5 pages

Java ArrayList Implementation Guide

This document provides code for implementing a list data structure using arrays in Java. It defines an interface for list operations like insertion, deletion, checking emptiness. An ArrayList class implements this interface using an array to store nodes, each containing a data element and pointer to the next node. Methods are provided to initialize the list, insert and delete elements from the front or after a specified position, find a node by its data, and check the size. A demo class shows example usage and output.

Uploaded by

omsohamom
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
59 views5 pages

Java ArrayList Implementation Guide

This document provides code for implementing a list data structure using arrays in Java. It defines an interface for list operations like insertion, deletion, checking emptiness. An ArrayList class implements this interface using an array to store nodes, each containing a data element and pointer to the next node. Methods are provided to initialize the list, insert and delete elements from the front or after a specified position, find a node by its data, and check the size. A demo class shows example usage and output.

Uploaded by

omsohamom
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

2.

Write Java programs to implement the following using arrays and linked lists
List ADT
a) List using Arrays
//[Link]
public interface List
{
public void createList(int n);
public void insertFirst(Object ob);
public void insertAfter(Object ob, Object pos);
public Object deleteFirst();
public Object deleteAfter(Object pos);
public boolean isEmpty();
public int size();
}
// [Link]
class ArrayList implements List
{
class Node
{
Object data;
int next;
Node(Object ob, int i) // constructor
{
data = ob;
next = i;
}
}
int MAXSIZE; // max number of nodes in the list
Node list[]; // create list array
int head, count; // count: current number of nodes in the list
ArrayList( int s) // constructor
{
MAXSIZE = s;
list = new Node[MAXSIZE];
}
public void initializeList()
{
for( int p = 0; p < MAXSIZE-1; p++ )
list[p] = new Node(null, p+1);
list[MAXSIZE-1] = new Node(null, -1);
}

public void createList(int n) // create n nodes


{
int p;
for( p = 0; p < n; p++ )
{
list[p] = new Node(11+11*p, p+1);
count++;
}
list[p-1].next = -1; // end of the list
}
public void insertFirst(Object item)
{
if( count == MAXSIZE )
{
[Link]("***List is FULL");
return;
}
int p = getNode();
if( p != -1 )
{
list[p].data = item;
if( isEmpty() ) list[p].next = -1;
else list[p].next = head;
head = p;
count++;
}
}
public void insertAfter(Object item, Object x)
{
if( count == MAXSIZE )
{
[Link]("***List is FULL");
return;
}
int q = getNode(); // get the available position to insert new node
int p = find(x); // get the index (position) of the Object x
if( q != -1 )
{
list[q].data = item;
list[q].next = list[p].next;
list[p].next = q;
count++;
}

}
public int getNode() // returns available node index
{
for( int p = 0; p < MAXSIZE; p++ )
if(list[p].data == null)
return p;
return -1;
}
public int find(Object ob) // find the index (position) of the Object ob
{
int p = head;
while( p != -1)
{
if( list[p].data == ob ) return p;
p = list[p].next; // advance to next node
}
return -1;
}
public Object deleteFirst()
{
if( isEmpty() )
{
[Link]("List is empty: no deletion");
return null;
}
Object tmp = list[head].data;
if( list[head].next == -1 ) // if the list contains one node,
head = -1; // make list empty.
else
head = list[head].next;
count--; // update count
return tmp;
}
public Object deleteAfter(Object x)
{
int p = find(x);
if( p == -1 || list[p].next == -1 )
{
[Link]("No deletion");
return null;
}
int q = list[p].next;
Object tmp = list[q].data;

list[p].next = list[q].next;
count--;
return tmp;
}
public void display()
{
int p = head;
[Link]("\nList: [ " );
while( p != -1)
{
[Link](list[p].data + " "); // print data
p = list[p].next; // advance to next node
}
[Link]("]\n");//
}
public boolean isEmpty()
{
if(count == 0) return true;
else return false;
}
public int size()
{
return count;
}
}
// [Link]
class ArrayListDemo
{
public static void main(String[] args)
{
ArrayList linkedList = new ArrayList(10);
[Link]();
[Link](4); // create 4 nodes
[Link](); // print the list
[Link]("InsertFirst 55:");
[Link](55);
[Link]();
[Link]("Insert 66 after 33:");
[Link](66, 33); // insert 66 after 33
[Link]();
Object item = [Link]();
[Link]("Deleted node: " + item);
[Link]();
[Link]("InsertFirst 77:");
[Link](77);
[Link]();

item = [Link](22); // delete node after node 22


[Link]("Deleted node: " + item);
[Link]();
[Link]("size(): " + [Link]());
}
}
OUTPUT:

You might also like