试图把AList和DLList结合起来,写出了一个混合链表
这样的混合链表有优势吗
CombineList
public class CombinedList<T>{
private DLList<T> node;
private AList<IntNode<T>> arraylist;
public CombinedList(T x){
node = new DLList<>(x);
arraylist = new AList<>();
arraylist.addLast(node.sentinelA.next);
}
public void addNum(int position,T x){
if(position < 0||position > arraylist.size){
throw new IndexOutOfBoundsException("Invalid index");
}
addNumHelper(position,x,node);
}
private void addNumHelper(int position,T x,DLList<T> node){
IntNode<T> tempNode = node.addNum(x,position);
arraylist.addNum(position,tempNode);
}
public void removeNum(int position){
removeNumHelper(position,node);
}
private void removeNumHelper(int position,DLList<T> node){
node.removeNum(position);
arraylist.removeNum(position);
}
public void setNum(T x,int position){
node.setNum(x, position);
}
public void printNum(){
node.printList();
}
public void getNum(int position){
node.getNum(position);
}
}
AList
public class AList<T> {
public int size;
public T[] item;
public AList(){
item = (T[]) new Object[100];
size = 0;
}
public void addLast(T x){
if(size == item.length){
resize(size * 2);
}
item[size] = x;
size++;
}
public void resize(int capacity){
T[] newArray = (T[]) new Object[capacity];
System.arraycopy(item,0,newArray,0,size);
item = newArray;
}
public T getLast(){
if(size == 0){
throw new IndexOutOfBoundsException("List is empty");
}
return item[size-1];
}
public T get(int position){
if(position < 0||position >= size){
throw new IndexOutOfBoundsException("Invalid index");
}
return item[position];
}
public int size(){
return size;
}
public T removeLast(){
if(size == 0){
throw new IndexOutOfBoundsException("List is empty");
}
T temp = item[size - 1];
item[size - 1] = null;
size--;
return temp;
}
public void set(int position,T x){
if(position < 0||position >= size){
throw new IndexOutOfBoundsException("Invalid index");
}
item[position] = x;
}
public void addNum(int position,T x){
if(position < 0||position > size){
throw new IndexOutOfBoundsException("Invalid index");
}
if(size == item.length){
resize(size * 2);
}
System.arraycopy(item,position,item,position+1,size-position);
item[position] = x;
size++;
}
public void removeNum(int position){
if(position < 0||position >= size){
throw new IndexOutOfBoundsException("Invalid index");
}
System.arraycopy(item,position+1,item,position,size-position-1);
item[--size] = null;
// 当利用率低于25%时缩容
if (size > 0 && size == item.length / 4) {
resize(item.length / 2);
}
}
}
DLList
public class DLList<T>{
public IntNode<T> sentinelA;
public IntNode<T> sentinelB;
public int size;
public IntNode<T> last;
public DLList(){
sentinelA = new IntNode<>(null,null,null);
sentinelB = new IntNode<>(null,null,null);
sentinelA.next = sentinelB;
sentinelB.prev = sentinelA;
size = 0;
last = sentinelA;
}
public DLList(T x){
this();
IntNode<T> node = new IntNode<>(sentinelA,x,sentinelB);
sentinelA.next = node;
sentinelB.prev = node;
last = node;
size = 1;
}
public void addFirst(T x){
IntNode<T> newNode = new IntNode<>(sentinelA,x,sentinelA.next);
sentinelA.next.prev = newNode;
sentinelA.next = newNode;
if(size == 0){
last = newNode;
}
size++;
}
public void addLast(T x){
if(size == 0){
addFirst(x);
return;
}
addLastHelper(x,sentinelA.next);
}
private void addLastHelper(T x,IntNode<T> node){
if(node.next == sentinelB){
IntNode<T> newNode = new IntNode<>(null,x,null);
node.next = newNode;
newNode.prev = node;
sentinelB.prev = newNode;
last = newNode;
size++;
return;
}
addLastHelper(x,node.next);
}
public IntNode<T> addNum(T x,int position){
if(position < 0||position >size){
throw new IndexOutOfBoundsException("Invalid index");
}
return addNumHelper(x,position,sentinelA);
}
private IntNode<T> addNumHelper(T x,int position,IntNode<T> pred){
if (position == 0) {
IntNode<T> succ = pred.next;
IntNode<T> newNode = new IntNode<>(pred, x, succ);
pred.next = newNode;
succ.prev = newNode;
size++;
last = (succ == sentinelB) ? newNode : last;//如果succ == sentinelB,则last = newNode,否则last不变
return newNode;
}
return addNumHelper(x, position - 1, pred.next);
}
public T removeLast(){
if(size == 0){
throw new IndexOutOfBoundsException("List is empty");
}
return removeLastHelper(sentinelA.next);
}
private T removeLastHelper(IntNode<T> node){
T temp;
temp = last.item;
last.prev.next = sentinelB;
sentinelB.prev = last.prev;
last = sentinelB.prev;
size--;
return temp;
}
public void removeNum(int position){
if(position < 0||position >=size){
throw new IndexOutOfBoundsException("Invalid index");
}
removeNumHelper(position,sentinelA.next);
}
private void removeNumHelper(int position,IntNode<T> node){
if(position == 0){
node.prev.next = node.next;
node.next.prev = node.prev;
last = sentinelB.prev;
size--;
return;
}
removeNumHelper(position - 1,node.next);
}
public IntNode<T> setNum(T x,int position){
IntNode<T> node1 = sentinelA.next;
while(position != 0){
position--;
node1 = node1.next;
}
node1.item = x;
return node1;
}
public void printList(){
printListHelper(sentinelA.next);
}
private void printListHelper(IntNode<T> node){
IntNode<T> current = node;
while(current != sentinelB){
System.out.println(current.item);
current = current.next;
}
}
public void getNum(int position){
IntNode<T> tempNode = sentinelA.next;
while(position != 0){
tempNode = tempNode.next;
position--;
}
System.out.println(tempNode.item);
}
}
IntNode
public class IntNode<T> {
public T item;
public IntNode<T> prev;
public IntNode<T> next;
public IntNode(IntNode<T> p,T i,IntNode<T> n){
prev = p;
item = i;
next = n;
}
}
