package com.nasuf.arraylist;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyLinkedList implements Iterable {
private int theSize;
private int modCount = 0;
private Node beginMarker;
private Node endMarker;
private static class Node {
public AnyType data;
public Node prev;
public Node next;
public Node(AnyType d, Node p, Node n) {
data = d;
prev = p;
next = n;
}
}
public MyLinkedList() {
clear();
}
public void clear() {
beginMarker = new Node (null, null, null);
endMarker = new Node (null, beginMarker, null);
beginMarker.next = endMarker;
theSize = 0;
modCount++;
}
public int size() {
return theSize;
}
public boolean isEmpty() {
return size() == 0;
}
public boolean add(AnyType x) {
add(size(), x);
return true;
}
public void add(int idx, AnyType x) {
addBefore(getNode(idx), x);
}
public AnyType get(int idx) {
return getNode(idx).data;
}
public AnyType set(int idx, AnyType newVal) {
Node p = getNode(idx);
AnyType oldVal = p.data;
p.data = newVal;
return oldVal;
}
public AnyType remove(int idx) {
return remove(getNode(idx));
}
private AnyType remove(Node p) {
p.next.prev = p.prev;
p.prev.next = p.next;
theSize --;
modCount ++;
return p.data;
}
private Node getNode(int idx) {
Node p;
if(idx < 0 || idx > size()) {
throw new IndexOutOfBoundsException();
}
if(idx < size() / 2) {
p = beginMarker.next;
for (int i=0; iidx; i++) {
p = p.prev;
}
}
return p;
}
private void addBefore(Node p, AnyType x) {
Node newNode = new Node(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
@Override
public Iterator iterator() {
return new LinkedListIterator();
}
private class LinkedListIterator implements java.util.Iterator {
private Node current = beginMarker.next;
private int expectedModCount = modCount;
private boolean okToRemove = false;
public boolean hasNext() {
return current != endMarker;
}
public AnyType next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (!hasNext())
throw new NoSuchElementException();
AnyType nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
public void remove() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (!okToRemove)
throw new IllegalStateException();
MyLinkedList.this.remove(current.prev);
okToRemove = false;
expectedModCount ++;
}
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/67381.html
