眠れずにアルゴリズムを書く(二)
4721 ワード
ループチェーンテーブル
package algorithms;
/**
*
* @author henry
* @date 2010-06-04 1:06:22
*/
public class MyLinkedList {
private static MyNode myNode;
private static int size = 0;
public MyLinkedList() {
// TODO Auto-generated constructor stub
myNode = new MyNode();
}
/**
*
* @param obj
*/
public void put(Object obj) {
if(size == 0) {
myNode.header = myNode;
myNode.put(obj);
myNode.next = myNode;
size++;
return;
}
MyNode node = new MyNode();
node.header = myNode.header;
node.put(obj);
node.next = myNode;
myNode.header.next = node;
myNode.header = node;
size++;
}
/**
*
* @return
*/
public int size() {
return size;
}
/**
*
* @param idx
* @return
*/
public Object get(int idx) {
if(idx >= size) {
throw new OutOfMemoryError();
}
MyNode mn = myNode;
Object obj = null;
for(int i = 0; i < size; i++) {
if(i == idx) {
obj = mn.get();
break;
}
mn = mn.next;
}
return obj;
}
/**
*
* @param idx
* @return
*/
public Object remove(int idx) {
if(idx >= size) {
throw new OutOfMemoryError();
}
MyNode mn = myNode;
Object obj = null;
if(idx == 0) {
obj = mn.get();
mn.next.header = mn.header;
myNode = mn.next;
mn = null;
size--;
return obj;
}
for(int i = 0; i < size; i++) {
if(i == idx) {
obj = mn.get();
mn.header.next = mn.next;
mn.next.header = mn.header;
size--;
mn = null;
break;
}
mn = mn.next;
}
return obj;
}
/**
*
* @param idx
* @return
*/
public Object reverse(int idx) {
if(idx >= size) {
throw new OutOfMemoryError();
}
MyNode mn = myNode.header;
Object obj = null;
if(idx == 0) {
obj = mn.get();
myNode.header = mn.header;
mn.header.next = mn.header;
mn = null;
size--;
return obj;
}
for(int i = 0; i < size; i++) {
if(i == idx) {
obj = mn.get();
mn.header.next = mn.next;
mn.next.header = mn.header;
size--;
mn = null;
break;
}
mn = mn.header;
}
return obj;
}
/**
*
* @param idx
* @return
*/
public Object getReverse(int idx) {
if(idx >= size) {
throw new OutOfMemoryError();
}
MyNode mn = myNode.header;
Object obj = null;
for(int i = 0; i < size; i++) {
if(i == idx) {
obj = mn.get();
break;
}
mn = mn.header;
}
return obj;
}
private static class MyNode {
private MyNode header;
private Object obj;
private MyNode next;
public MyNode() {
// TODO Auto-generated constructor stub
header = null;
obj = null;
next = null;
}
public void put(Object o) {
obj = o;
}
public Object get() {
return this.obj;
}
}
public static void main(String[] args) {
MyLinkedList mll = new MyLinkedList();
for(int i = 0; i < 10; i++) {
mll.put(i + "");
}
for(int i = 0; i < mll.size(); i++) {
String a = (String) mll.get(i);
System.out.print(a + " ");
}
System.out.println();
System.out.println(" :" + mll.size());
System.out.println(mll.remove(0));
System.out.println(mll.size());
for(int i = 0; i < mll.size(); i++) {
String a = (String) mll.get(i);
System.out.print(a + " ");
}
System.out.println();
System.out.println(mll.reverse(5));
System.out.println(mll.size());
for(int i = 0; i < mll.size(); i++) {
String a = (String) mll.getReverse(i);
System.out.print(a + " ");
}
}
}