Skip to content

Instantly share code, notes, and snippets.

@jimmykurian

jimmykurian/ArrayListImp.java

Created May 4, 2012 20:31
Show Gist options
  • Save jimmykurian/2597534 to your computer and use it in GitHub Desktop.
Save jimmykurian/2597534 to your computer and use it in GitHub Desktop.
Download ZIP
A java program that contains implementations of the ArrayList and LinkedList classes and various custom written methods.
Raw
ArrayListImp.java
//ArrayListImp.java - Jimmy Kurian
import java.util.Iterator;
public class ArrayListImp<E>
{
private E [ ] items;
private int capacity = 2;
private int size = 0;
public ArrayListImp()
{
items = (E [ ]) new Object[capacity];
}
public Iterator<E> iterator()
{
return new Iterator<E>()
{
int position = 0;
public boolean hasNext()
{
return position < size;
}
public E next(){
return items[position++];
}
public void remove()
{
size--;
items[position-1] = items[size];
}
}
}
public boolean add(E newItem)
{
if (size + 1 == capacity) expandArray();
items[size++] = newItem;
return true;
}
public boolean add(int index, E newItem)
{
if (index > size) return false;
if (size == capacity) expandArray();
for (int i=size; i>index; i--)
items[i] = items[i-1];
items[index] = newItem;
size++;
return true;
}
public boolean equals(Object obj)
{
ArrayListImp<E> anotherList = (ArrayListImp<E>) obj;
Iterator it = items.iterator();
while (it.hasNext())
{
if (items.equals(anotherList)
{
return true;
}
else
{
return false;
}
}
}
public boolean remove(E item)
{
for (int i=0; i<size; i++)
if (items[i].equals(item))
{
for (int j=i+1; j<size; j++)
items[j-1] = items[j];
size--;
return true;
}
return false;
}
public boolean remove(int index)
{
if (index >= size) return false;
for (int i=index+1; i<size; i++)
items[i-1] = items[i];
size--;
return true;
}
public boolean contains(E item) {
for (int i=0; i<size; i++)
if (items[i].equals(item))
return true;
return false;
}
private void expandArray()
{
capacity *= 2;
E [ ] newItems = (E [ ] ) new Object[capacity];
for (int i=0; i<size; i++)
newItems[i] = items[i];
items = newItems;
}
public String toString()
{
String answer = "[ ";
for (int i=0; i<size; i++)
answer += items[i] + " ";
return answer + "]";
}
}
Raw
LinkedListImp.java
//LinkedListImp.java - Jimmy Kurian
public class LinkedListImp<E> {
private int size;
private NodeImp<E> front;
private NodeImp<E> back;
public LinkedListImp() {
front = new NodeImp<E>();
back = new NodeImp<E>();
front.setNext(back);
front.setPrevious(null);
back.setNext(null);
back.setPrevious(front);
}
public Iterator<E> iterator()
{
current = head;
public boolean hasNext()
{
return (current != null);
}
public E next()
{
if (hasNext())
{
E result = current.item;
current = current.next;
return result;
}
throw new java.util.NoSuchElementException("No other element.");
}
public void remove()
{
for (int i = current; i != null, i++()
{
if (current.next == item)
{
if (current.previous == null)
{
head = current.next;
}
else if (current.next == null)
{
current.previous = setNext(null);
}
else
{
current.previous = setNext(current.next);
current.next = setPrevious(current.previous);
}
E remove(current);
return true;
}
}
}
public boolean equals(Object obj)
{
LinkedListImp<E> anotherList = (LinkedListImp<E>) obj;
NodeImp<E> current = this;
Iterator it = current.iterator();
while (it.hasNext())
{
if (current.equals(anotherList)
{
return true;
}
else
{
return false;
}
}
}
public boolean add(E item) {
return front.add(item);
}
public boolean add(int index, E item) {
return front.add(index,item);
}
public boolean remove(E item) {
return front.remove(item);
}
public boolean remove(int index) {
return front.remove(index);
}
public E set(int index, E item) {
return front.set(index, item);
}
public E get(int index) {
return front.get(index);
}
public String toString() {
return front.getNext().toString();
}
class NodeImp<E> {
private E data;
private NodeImp<E> next;
private NodeImp<E> previous;
public NodeImp() { }
public NodeImp(E item) {
data = item;
next = null;
previous = null;
}
public E getData() { return data; }
public void setData(E item) {
data = item;
}
public NodeImp<E> getNext() { return next; }
public void setNext(NodeImp<E> n) {
next = n;
}
public NodeImp<E> getPrevious() { return previous; }
public void setPrevious(NodeImp<E> n) {
previous = n;
}
public boolean add(E item) {
NodeImp<E> newNode = new NodeImp<E>(item);
NodeImp<E> current = this;
NodeImp<E> next = current.getNext();
while (next != back) {
current = next;
next = next.getNext();
}
current.setNext(newNode);
newNode.setPrevious(current);
newNode.setNext(next);
next.setPrevious(newNode);
return true;
}
public boolean add(int index, E item) {
NodeImp<E> newNode = new NodeImp<E>(item);
NodeImp<E> current = this;
for (int i=0; i<index; i++) {
current = current.getNext();
if (current == back) return false;
}
newNode.setNext(current.getNext());
current.getNext().setPrevious(newNode);
current.setNext(newNode);
newNode.setPrevious(current);
return true;
}
public boolean remove(E item) {
NodeImp<E> current = getNext();
while (!current.getData().equals(item)) {
current = current.getNext();
if (current == back) return false;
}
current.getPrevious().setNext(current.getNext());
current.getNext().setPrevious(current.getPrevious());
return true;
}
public boolean remove(int index) {
NodeImp<E> current = getNext();
for (int i=0; i<index; i++) {
current = current.getNext();
if (current == back || current == null) return false;
}
current.getPrevious().setNext(current.getNext());
current.getNext().setPrevious(current.getPrevious());
return true;
}
public E set(int index, E newItem) {
NodeImp<E> current = this;
for (int i=0; i<index; i++)
current = current.getNext();
E oldItem = current.getData();
current.setData(newItem);
return oldItem;
}
public E get(int index) {
NodeImp<E> current = this;
for (int i=0; i<index; i++)
current = current.getNext();
return current.getData();
}
public String toString() {
String answer = "[ ";
for (NodeImp<E> current = this; current != back;
current = current.getNext())
answer += current.getData() + " ";
return answer + "]";
}
}
}
Raw
NodeImp.java
//NodeImp.java - Jimmy Kurian
public class NodeImp<E> {
private E data;
private NodeImp<E> next;
public NodeImp() { }
public NodeImp(E item) {
data = item;
next = null;
}
public E getData() { return data; }
public void setData(E item) {
data = item;
}
public NodeImp<E> getNext() { return next; }
public void setNext(NodeImp<E> n) {
next = n;
}
public boolean add(E item) {
NodeImp<E> newNode = new NodeImp<E>(item);
NodeImp<E> current = this;
NodeImp<E> next = current.getNext();
while (next != null) {
current = next;
next = next.getNext();
}
current.setNext(newNode);
return true;
}
public boolean add(int index, E item) {
NodeImp<E> current = this;
if (index == 0) return false;
for (int i=1; i<index; i++) {
current = current.getNext();
if (current == null) return false;
}
NodeImp<E> newNode = new NodeImp<E>(item);
newNode.setNext(current.getNext());
current.setNext(newNode);
return true;
}
public boolean remove(E item) {
if (item.equals(getData())) return false;
NodeImp<E> previous = this,
current = getNext();
while (!current.getData().equals(item)) {
previous = current;
current = current.getNext();
if (current == null) return false;
}
previous.setNext(current.getNext());
return true;
}
public boolean remove(int index) {
if (index == 0) return false;
NodeImp<E> previous = this,
current = getNext();
for (int i=1; i<index; i++) {
previous = current;
current = current.getNext();
if (current == null) return false;
}
previous.setNext(current.getNext());
return true;
}
public E set(int index, E newItem) {
NodeImp<E> current = this;
for (int i=0; i<index; i++)
current = current.getNext();
E oldItem = current.getData();
current.setData(newItem);
return oldItem;
}
public E get(int index) {
NodeImp<E> current = this;
for (int i=0; i<index; i++)
current = current.getNext();
return current.getData();
}
public String toString() {
String answer = "[ ";
for (NodeImp<E> current = this; current != null; current = current.getNext())
answer += current.getData() + " ";
return answer + "]";
}
}
Raw
UseArrayListImp.java
//UseArrayListImp.java - Jimmy Kurian
import java.util.Scanner;
public class UseArrayListImp {
public static void main(String [ ] args) {
ArrayListImp<String> theList = new ArrayListImp<String>();
int option = 0;
int index;
Scanner input = new Scanner(System.in);
System.out.println("\n\n\nList = " + theList);
while (true) {
System.out.println("Enter operation (1 = add at end; 2 = add at index; 3 = remove item; 4 = remove at index; 5 = quit)");
option = input.nextInt();
switch (option) {
case 1:
System.out.println("Enter string:");
System.out.println("Add returns " + theList.add(input.next()));
System.out.println("List = " + theList);
break;
case 2:
System.out.println("Enter index:");
index = input.nextInt();
System.out.println("Enter string:");
System.out.println("Add returns " + theList.add(index, input.next()));
System.out.println("List = " + theList);
break;
case 3:
System.out.println("Enter string:");
System.out.println("Remove returns " + theList.remove(input.next()));
System.out.println("List = " + theList);
break;
case 4:
System.out.println("Enter index:");
index = input.nextInt();
System.out.println("Remove returns " + theList.remove(index));
System.out.println("List = " + theList);
break;
case 5:
return;
default:
System.out.println("Invalid option");
}
}
}
}
Raw
UseLinkedListImp.java
//UseLinkedListImp.java - Jimmy Kurian
import java.util.Scanner;
public class UseLinkedListImp {
public static void main(String [ ] args) {
LinkedListImp<String> theList = new LinkedListImp<String>();
int option = 0;
int index;
Scanner input = new Scanner(System.in);
System.out.println("\n\n\nList = " + theList);
while (true) {
System.out.println("Enter operation (1 = add at end; 2 = add at index; 3 = remove item; 4 = remove at index; 5 = quit)");
option = input.nextInt();
switch (option) {
case 1:
System.out.println("Enter string:");
System.out.println("Add returns " + theList.add(input.next()));
System.out.println("List = " + theList);
break;
case 2:
System.out.println("Enter index:");
index = input.nextInt();
System.out.println("Enter string:");
System.out.println("Add returns " + theList.add(index, input.next()));
System.out.println("List = " + theList);
break;
case 3:
System.out.println("Enter string:");
System.out.println("Remove returns " + theList.remove(input.next()));
System.out.println("List = " + theList);
break;
case 4:
System.out.println("Enter index:");
index = input.nextInt();
System.out.println("Remove returns " + theList.remove(index));
System.out.println("List = " + theList);
break;
case 5:
return;
default:
System.out.println("Invalid option");
}
}
}
}
Raw
UseNodeImp.java
//UseNodeImp.java - Jimmy Kurian
import java.util.Scanner;
public class UseNodeImp {
public static void main(String [ ] args) {
NodeImp<String> theList = new NodeImp<String>("x");
int option = 0;
int index;
Scanner input = new Scanner(System.in);
System.out.println("\n\n\nList = " + theList);
while (true) {
System.out.println("Enter operation (1 = add at end; 2 = add at index; 3 = remove item; 4 = remove at index; 5 = quit)");
option = input.nextInt();
switch (option) {
case 1:
System.out.println("Enter string:");
System.out.println("Add returns " + theList.add(input.next()));
System.out.println("List = " + theList);
break;
case 2:
System.out.println("Enter index:");
index = input.nextInt();
System.out.println("Enter string:");
System.out.println("Add returns " + theList.add(index, input.next()));
System.out.println("List = " + theList);
break;
case 3:
System.out.println("Enter string:");
System.out.println("Remove returns " + theList.remove(input.next()));
System.out.println("List = " + theList);
break;
case 4:
System.out.println("Enter index:");
index = input.nextInt();
System.out.println("Remove returns " + theList.remove(index));
System.out.println("List = " + theList);
break;
case 5:
return;
default:
System.out.println("Invalid option");
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment