[データ構造とアルゴリズム]-Javaで簡単なLinkdListを実現する
17325 ワード
この文章は転載を歓迎します.転載する前に、作者に連絡してください.転載後は出典を明記してください.ありがとうございます.http://blog.csdn.net/colton_null作者:お酒を飲んで、乗馬しません.Null from CSDN
一.はじめに
本稿では、簡単なArayListを独自に実現するためのコードを共有し、主に「データ構造とアルゴリズム分析」を参照している.
二.実現が必要な内容 MyLinkdList():双方向リンク を初期化する. size():リターンチェーン長 isEmpty():チェーンが空かどうかを判断する add():末尾の に要素を追加します. add(int index,T t):指定されたインデックスに要素を追加する get(int index):指定された索引の要素 を取得する. set(int index,T t):指定された索引の要素を置換する Remove(index):指定されたインデックスの要素を除去する iterator():このチェーンを獲得するためのシーズマリー 三.MyLinked Listコード
考え方も方法もコメントに書いてあります.
考え方も方法も同じように注釈に書いてあります.
前人の肩に立ち、次のブログや文献のサポートに感謝します.『データ結果とアルゴリズム分析機械工業出版社』
一.はじめに
本稿では、簡単なArayListを独自に実現するためのコードを共有し、主に「データ構造とアルゴリズム分析」を参照している.
二.実現が必要な内容
考え方も方法もコメントに書いてあります.
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyLinkedList<T> implements Iterable<T> {
private int theSize;
private int modCount;
private Node beginMarker;
private Node endMarker;
public MyLinkedList() {
clear();
}
/**
*
*/
private void clear() {
beginMarker = new Node(null, null, null);
endMarker = new Node(null, beginMarker, null);
beginMarker.next = endMarker;
theSize = 0;
modCount++;
}
/**
*
*
* @return
*/
public int size() {
return theSize;
}
/**
*
*
* @return true， false
*/
public boolean isEmpty() {
return size() == 0;
}
/**
*
*
* @param t
* @return
*/
public boolean add(T t) {
add(size(), t);
return true;
}
/**
*
*
* @param index
* @param t
*/
public void add(int index, T t) {
// getNode size() ， ， 。
// size() - 1 ， getNode IndexOutOfBoundsException
addBefore(getNode(index, 0, size()), t);
}
/**
* node node
*
* @param p node
* @param t node
*/
private void addBefore(Node p, T t) {
Node newNode = new Node<>(t, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
/**
*
*
* @param index
* @return
*/
public T get(int index) {
return getNode(index).data;
}
/**
*
*
* @param index
* @param t
* @return
*/
public T set(int index, T t) {
Node node = getNode(index);
T oldValue = node.data;
node.data = t;
return oldValue;
}
/**
*
*
* @param index
* @return
*/
public T remove(int index) {
return remove(getNode(index));
}
/**
*
*
* @param p
* @return
*/
private T remove(Node p) {
p.prev.next = p.next;
p.next.prev = p.prev;
modCount++;
theSize--;
return p.data;
}
/**
*
*
* @param index
* @return
*/
private Node getNode(int index) {
return getNode(index, 0, size() - 1);
}
/**
* index 。 。
*
* @param index
* @param lower
* @param upper
* @return
*/
private Node getNode(int index, int lower, int upper) {
Node p;
if (index < lower || index > upper) {
throw new IndexOutOfBoundsException();
}
// ， 。 。
if (index < size() / 2) {
p = beginMarker.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
} else {
p = endMarker;
for (int i = size(); i > index; i--) {
p = p.prev;
}
}
return p;
}
@Override
public String toString() {
String str = "";
Node p = beginMarker;
while (p.next != endMarker) {
str += p.next.data.toString() + "
";
p = p.next;
}
return str;
}
@Override
public Iterator iterator() {
return new LinkedListIterator();
}
/**
* Node
*
* @param
*/
private class Node<T> {
//
public T data;
//
public Node prev;
//
public Node next;
public Node(T d, Node p, Node n) {
data = d;
prev = p;
next = n;
}
}
private class LinkedListIterator implements Iterator<T> {
// 。 beginMarker.next，
private Node current = beginMarker.next;
// 。 modCount 。
private int expectedModCount = modCount;
//
private boolean okToRemove = false;
/**
* 。 endMarker， 。
* @return
*/
@Override
public boolean hasNext() {
return current != endMarker;
}
/**
*
* @return
*/
@Override
public T next() {
// ，
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
T nextItem = current.data;
current = current.next;
// true
okToRemove = true;
return nextItem;
}
/**
*
*/
@Override
public void remove() {
// ，
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (!okToRemove) {
throw new IllegalStateException();
}
MyLinkedList.this.remove(current.prev);
// modCount
expectedModCount++;
// false
okToRemove = false;
}
}
} 考え方も方法も同じように注釈に書いてあります.
import java.util.Iterator;
public class MyLinkedListTest {
public static void main(String[] args) {
// MyLinkedList
MyLinkedList list = new MyLinkedList<>();
System.out.println("list :" + list.size());
System.out.println("list :" + list.isEmpty());
//
list.add(1);
list.add(2);
System.out.println("list :" + list.size());
System.out.println("list :" + list.isEmpty());
System.out.println("list :");
System.out.println(list);
//
list.add(0, 100);
System.out.println("list :" + list.get(0));
//
list.set(0, 200);
System.out.println("list :" + list.get(0));
//
list.remove(1);
System.out.println("list :");
System.out.println(list);
//
Iterator itr = list.iterator();
System.out.println(" list:");
while (itr.hasNext()) {
System.out.println(itr.next());
}
//
itr = list.iterator();
while (itr.hasNext()) {
itr.next();
itr.remove();
}
System.out.println("list :" + list.isEmpty());
}
} list :0
list :true
list :2
list :false
list :
1
2
list :100
list :200
list :
200
2
list:
200
2
list :true前人の肩に立ち、次のブログや文献のサポートに感謝します.