データ構造(2)シングルチェーンとサイクルチェーン表
11878 ワード
チェーン?テーブル
public class SingleLinkedList extends AbstractList {
private Node first;
private static class Node {
E element;
Node next;
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E get(int index) {
/*
* ：O(1)
* ：O(n)
* ：O(n)
*/
return node(index).element;
}
@Override
public E set(int index, E element) {
/*
* ：O(1)
* ：O(n)
* ：O(n)
*/
Node node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
/*
* ：O(1)
* ：O(n)
* ：O(n)
*/
rangeCheckForAdd(index);
if (index == 0) {
first = new Node<>(element, first);
} else {
Node prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
@Override
public E remove(int index) {
/*
* ：O(1)
* ：O(n)
* ：O(n)
*/
rangeCheck(index);
Node node = first;
if (index == 0) {
first = first.next;
} else {
Node prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* index
* @param index
* @return
*/
private Node node(int index) {
rangeCheck(index);
Node node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
// Node node1 = first;
// while (node1 != null) {
//
//
// node1 = node1.next;
// }
return string.toString();
}
}
public class SingleCircleLinkedList extends AbstractList {
private Node first;
private static class Node {
E element;
Node next;
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(element).append("_").append(next.element);
return sb.toString();
}
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == 0) {
Node newFirst = new Node<>(element, first);
//
Node last = (size == 0) ? newFirst : node(size - 1);
last.next = newFirst;
first = newFirst;
} else {
Node prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node node = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
Node last = node(size - 1);
first = first.next;
last.next = first;
}
} else {
Node prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* index
* @param index
* @return
*/
private Node node(int index) {
rangeCheck(index);
Node node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
}
public class CircleLinkedList extends AbstractList {
private Node first;
private Node last;
private Node current;
private static class Node {
E element;
Node prev;
Node next;
public Node(Node prev, E element, Node next) {
this.prev = prev;
this.element = element;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (prev != null) {
sb.append(prev.element);
} else {
sb.append("null");
}
sb.append("_").append(element).append("_");
if (next != null) {
sb.append(next.element);
} else {
sb.append("null");
}
return sb.toString();
}
}
public void reset() {
current = first;
}
public E next() {
if (current == null) return null;
current = current.next;
return current.element;
}
public E remove() {
if (current == null) return null;
Node next = current.next;
E element = remove(current);
if (size == 0) {
current = null;
} else {
current = next;
}
return element;
}
@Override
public void clear() {
size = 0;
first = null;
last = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
// size == 0
// index == 0
if (index == size) { //
Node oldLast = last;
last = new Node<>(oldLast, element, first);
if (oldLast == null) { //
first = last;
first.next = first;
first.prev = first;
} else {
oldLast.next = last;
first.prev = last;
}
} else {
Node next = node(index);
Node prev = next.prev;
Node node = new Node<>(prev, element, next);
next.prev = node;
prev.next = node;
if (next == first) { // index == 0
first = node;
}
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
return remove(node(index));
}
private E remove(Node node) {
if (size == 1) {
first = null;
last = null;
} else {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
if (node == first) { // index == 0
first = next;
}
if (node == last) { // index == size - 1
last = prev;
}
}
size--;
return node.element;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* index
* @param index
* @return
*/
private Node node(int index) {
rangeCheck(index);
if (index < (size >> 1)) {
Node node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
Node node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
}