簡單來說其實使用數組模擬LinkedList。同LinkedList的操作基本相似。?
基本原理為：數組存放Entry對象，包含數據部分，指針部分(數組下標)?
添加，刪除基本操作改變指針。數組包含兩個鏈表，一個備用鏈表(空數據，僅含指針)與?
實際存放數據的鏈表(即保存存入的數)。添加先從備用鏈表中獲取一個空閑節點，?
移除把節點重新放入備用鏈表等待獲取。采用ArrayList的數組自動擴張的方法。?
具體代碼如下：? package com.utils;


import java.util.AbstractSequentialList;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;








/**
?* 用數組模擬雙向循環列表
?*/
public class ArrayLinkedList<E> extends AbstractSequentialList<E> implements?
List<E>{

//空閑鏈表頭結點,索引為0的位置設置頭結點
private transient Entry<E> freeHeader;
//實際鏈表頭結點，索引為1的位置設置頭結點
private transient Entry<E> header;
private transient int size = 0; //數組中存儲的Entry對象個數

private transient Object[] data; //Object數組，因為java不支持泛型數組，即Entry<E>[] data = new Entry<E>[10] //error
//遍歷時進行強制類型轉換即可
/**
* 構造方法一，初始化化數組?
*/
public ArrayLinkedList(int initialCapacity) {
super();
? ? ? ? if (initialCapacity < 0)
? ? ? ? ? ? throw new IllegalArgumentException("Illegal Capacity: "+
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?initialCapacity);
? ? ? ? initArray(initialCapacity);
}

/**
* 構造方法二，構造含有指定集合c中所有元素的鏈表
* 具體見addAll方法
*/
public ArrayLinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

/**
* 默認數組長度
*/
public ArrayLinkedList(){
this(10);
}

/**
* 初始化數組.
* 除header，其他都是備用鏈表的元素
* 實際鏈表此時為空。數據項都為空
*/
private void initArray(int initialCapacity) {
data = new Object[initialCapacity];
for(int i = 0 ;i < data.length;i++){
if(freeHeader==null){
freeHeader = new Entry<E>(null, i, i+2, data.length-1);
data[i] = freeHeader;
continue;
}
if(header == null){
header = new Entry<E>(null, i, i, i); //初始實際鏈表頭結點,此鏈表為空
data[i] = header;
continue;
}
Entry<E> e = new Entry<E>(null, i,?
i+1==data.length ? 0 : i+1, i-1 == 1 ? 0 : i-1);
data[i] = e;
}
}

/**
* 獲取一個備用鏈表的節點
* */
public int getFreeNode(){
int i = freeHeader.next;
if(i > 0 ){
Entry e = (Entry)data[i];
freeHeader.next = e.next;
((Entry)data[e.next]).pre = freeHeader.cur;
}
return i;
}

/**
* 將空閑節點回收到備用鏈表
* */
public void free(Entry<E> e){
e.next ?= freeHeader.next;
e.pre = freeHeader.cur;
freeHeader.next = e.cur;
e.element = null;
}

public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = data.length;
if (minCapacity > oldCapacity) {
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
data = Arrays.copyOf(data, newCapacity);
//初始化增加的節點
for(int i = oldCapacity; i < newCapacity;i++){
Entry<E> e = new Entry<E>(null, i,?
i+1==data.length ? 0 : i+1, i-1 == 1 ? 0 : i-1);
data[i] = e;
//修改備用頭結點
freeHeader.pre = newCapacity - 1;
freeHeader.next = oldCapacity;
}
}
}


public E getFirst(){
if(size == 0)
throw new NoSuchElementException();
return ((Entry<E>)data[header.next]).element;
}

public E getLast(){
if(size == 0)
throw new NoSuchElementException();
return ?((Entry<E>)data[header.pre]).element;
}

/**
* 移除第一個元素，具體見remove()方法
*/
public E removeFirst() {
return remove((Entry<E>)data[header.next]);
}


/**
* 移除最后一個元素
*/
public E removeLast() {
return remove((Entry<E>)data[header.pre]);
}

/**
*?
* 在鏈表開始位置添加一個元素
* 詳情見addBefore()
*/
public void addFirst(E e) {
addBefore(e, (Entry<E>)data[header.next]);
}


/**
* 在鏈表最后位置添加一個元素
* 詳情見addBefore()
*/
public void addLast(E e) {
addBefore(e, header);
}

/**
* 查看鏈表是否包含元素o
* 詳細見indexOf()方法
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}

/**
*?
* 返回o第一次出現的位置，如果在List中找不到o返回-1
*/
public int indexOf(Object o) {
int index = 0; //鏈表的索引也是從0開始
if (o == null) {
for (Entry e = (Entry)data[header.next]; e != header; e = (Entry)data[e.next]) { //從頭結點開始，依次遍歷
if (e.element == null)
return index;
index++;
}
} else {
for (Entry e = (Entry)data[header.next]; e != header; e = (Entry)data[e.next]) {
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
}

/**
* 雙向循環鏈表，從后面開始遍歷即可
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Entry e = (Entry)data[header.pre]; e != header; e = (Entry)data[e.pre]) {
index--;
if (e.element == null)
return index;
}
} else {
for (Entry e = (Entry)data[header.pre]; e != header; e = e = (Entry)data[e.pre]) {
index--;
if (o.equals(e.element))
return index;
}
}
return -1;
}


/**
* 跟addLast()方法類似，添加成功返回true
*/
public boolean add(E e) {
addBefore(e, header);
return true;
}

/**
* 假如鏈表中含有一個或多個o對象，移除第一次出現的o
* 如果找不到o返回false
*/
public boolean remove(Object o) {
if (o == null) {
for (Entry<E> e = (Entry<E>)data[header.next]; e != header; e = (Entry<E>)data[e.next]) { //從第一個元素開始遍歷，沒一個Entry對象都包含它下一個元素的信息
if (e.element == null) {
remove(e);
return true;
}
}
} else {
for (Entry<E> e = (Entry<E>)data[header.next]; e != header; e = (Entry<E>)data[e.next]) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}

/**
*?
* 把c中所有元素按順序添加到鏈表尾部
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}

/**
*?
* 在指定位置按順序添加c中所有元素帶List中
*?
*/
public boolean addAll(int index, Collection<? extends E> c) {
if (index < 0 || index > size) //檢查是否越界，=size表示添加到最后
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
ensureCapacity(size + numNew + 2);


Entry<E> successor = (index == size ? header : entry(index));
Entry<E> predecessor = (Entry<E>)data[successor.pre];
for (int i = 0; i < numNew; i++) { //這里不難，畫一個圖就出來了，主要是初始化c和修改指針
//暫時使其next為successor，因為e會賦給前驅,而每次遍歷都要修改其前驅的next
int node = getFreeNode();
Entry<E> e = (Entry<E>)data[node];
e.next = successor.cur;
e.pre = predecessor.cur;
e.element = (E)a[i];
predecessor.next = e.cur; ? //重新設置前驅的next指針
predecessor = e; //讓e變為前驅
}
successor.pre = predecessor.cur; //successor的前驅為c中最后一個元素的引用


size += numNew; //長度加
return true;
}

/**
* 移除鏈表中所有元素
*/
public void clear() {
Entry<E> e = (Entry<E>)data[header.next];
while (e != header) { //表示不是只有一個頭結點的空鏈表
Entry<E> next = (Entry<E>)data[e.next];
free(e);
e = next;
}
header.next = header.pre = header.cur = 1; //初始頭結點
size = 0;
modCount++;
}

/**
* 返回指定位置的元素時
*/
public E get(int index) {
return entry(index).element;
}


/**
* 設置指定位置的元素
*/
public E set(int index, E element) {
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}

/**
*?
* 把指定元素添加到指定位置，需先定位到此位置的節點
* 詳情見addBefore()
*/
public void add(int index, E element) {
addBefore(element, (index == size ? header : entry(index)));
}


/**
* 移除指定位置的元素
*/
public E remove(int index) {
return remove(entry(index));
}

/**
*?
* 返回指定索引位置的Entry對象，需要依次遍歷得到。
* 這里稍做了一下優化，如果index < size/2 從前面開始遍歷
* 如果index >= size/2 從后面開始遍歷
*/
private Entry<E> entry(int index) {
if (index < 0 || index >= size) //index在0(包含)到size(不包含)之間，索引從0開始
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = (Entry<E>)data[e.next]; //依次調用e.next才能得到,需調用index+1次，因為它是從頭結點開始的
} else {
for (int i = size; i > index; i--)
e = (Entry<E>)data[e.pre]; //依次調用e.previous才能得到
}
return e;
}


private Entry<E> addBefore(E e,Entry<E> entry){
ensureCapacity(size + 1 + 2);
int node = getFreeNode();
Entry<E> newEntry = (Entry<E>)data[node];
newEntry.element = e;
newEntry.cur = node;
newEntry.pre = entry.pre;
newEntry.next = entry.cur;

((Entry<E>)data[newEntry.pre]).next = node;
((Entry<E>)data[newEntry.next]).pre = node;
size++;
return newEntry;
}

private E remove(Entry<E> e){
if(e == header)
throw new NoSuchElementException();
E result = e.element;
//改變實際鏈表的節點指針
((Entry<E>)data[e.pre]).next = e.next;
((Entry<E>)data[e.next]).pre = e.pre;
free(e);
size--; //size--
modCount++;
return result;
}

@Override
public ListIterator<E> listIterator(int index) {
return new ListItr(index);
}


@Override
public int size() {
// TODO Auto-generated method stub
return size;
}



private static class Entry<E>{
E element;
int next;
int pre;
int cur;

Entry(E element,int cur,int next,int pre){
this.element = element;
this.next = next;
this.pre = pre;
this.cur = cur;
}
public String toString(){
return "element:"+ element +" cur:"+cur+" next:"+next+" pre:"+pre;
}
}



private class ListItr implements ListIterator<E> {
private Entry<E> lastReturned = header; //上一次調用next或previous返回的元素，沒有調用next則為頭結點
private Entry<E> next; //下一次調用next方法返回的元素
private int nextIndex; //下一次調用next返回的元素的索引
private int expectedModCount = modCount; //用來檢測遍歷過程中是否產生了并發操作


ListItr(int index) { //構造器，是迭代器定位到index位置，要返回index位置的元素需調用一次next()方法時
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index
+ ", Size: " + size);
if (index < (size >> 1)) { //從前面開始遍歷
next = (Entry<E>)data[header.next]; //這是index為0的元素
for (nextIndex = 0; nextIndex < index; nextIndex++)
next = (Entry<E>)data[next.next]; //最終next為第index個元素，index從0開始
} else { //從后面開始遍歷
next = header;
for (nextIndex = size; nextIndex > index; nextIndex--)
next = (Entry<E>)data[next.pre]; //最終next為第index個元素，index從0開始
}
}


public boolean hasNext() { //size位置可沒有元素
return nextIndex != size;
}


public E next() {
checkForComodification();
if (nextIndex == size)
throw new NoSuchElementException();


lastReturned = next;
next = (Entry<E>)data[next.next]; //這里與ArrayList中的cursor何其相似
nextIndex++;
return lastReturned.element;
}


public boolean hasPrevious() {
return nextIndex != 0;
}


public E previous() {
if (nextIndex == 0)
throw new NoSuchElementException();


lastReturned = next = (Entry<E>)data[next.pre];
nextIndex--;
checkForComodification();
return lastReturned.element;
}


public int nextIndex() { //返回下一次調用next返回的元素的索引
return nextIndex;
}


public int previousIndex() { //返回下一次調用previous返回的元素的索引
return nextIndex - 1;
}


public void remove() {
checkForComodification();
Entry<E> lastNext = (Entry)data[lastReturned.next];
try {
ArrayLinkedList.this.remove(lastReturned); //移除上一層調用next()或previous返回的元素
} catch (NoSuchElementException e) {
throw new IllegalStateException();
}
if (next == lastReturned) //表明是調用previous后才調用remove方法
next = lastNext;
else
nextIndex--; //元素減少。nextIndex--
lastReturned = header; //重置lastReturned
expectedModCount++;
}


public void set(E e) {
if (lastReturned == header)
throw new IllegalStateException();
checkForComodification();
lastReturned.element = e;
}


public void add(E e) {
checkForComodification();
lastReturned = header;
addBefore(e, next); //在上一次調用next返回的元素之后，在上次調用previous返回的元素之前添加e
nextIndex++; //元素增加，索引增加，保證下次調用next()不是返回添加的元素
expectedModCount++;
}


final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}

總結

以上是生活随笔為你收集整理的用动态数组模拟双向循环链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。