如果你有许多list，这里将会是大量的时间，我指的是对于单向链表查找时间复杂度O(N)相对于数组O(1)的时间复杂度会慢一些
所以这究竟是顺序表的编写还是链表的改进?
IntList
public class IntList {public int first;public IntList rest;public IntList(int f, IntList r) {first = f;rest = r;}/** Return the size of the list using... recursion! */public int size() {if (this.rest == null) {/* base case */return 1;}return 1 + this.rest.size();}/** Return the size of the list using no recursion! */public int iterativeSize() {/* You can not assign "this" in Java*/IntList p = this;int totalSize = 0;while (p != null) {totalSize += 1;p = p.rest;}return totalSize;}/** Returns the ith value in this list.*/public int get(int i) {IntList p = this;int nth = 0;if (i >= p.size()) {return -1;}while (nth != i) {p = p.rest;nth += 1;}return p.first;}public static void main(String[] args) {IntList L = new IntList(15, null);L = new IntList(10, L);L = new IntList(5, L);System.out.println(L.size());System.out.println(L.iterativeSize());System.out.println(L.get(2));}
} SLList
/** An SLList is a list of integers, which hides the terrible truth* of the nakedness within. */
public class SLList { private static class IntNode {public int item;public IntNode next;public IntNode(int i, IntNode n) {item = i;next = n;System.out.println(size);}} /* The first item (if it exists) is at sentinel.next. */private IntNode sentinel;private int size;private static void lectureQuestion() {SLList L = new SLList();IntNode n = IntNode(5, null);}/** Creates an empty SLList. */public SLList() {sentinel = new IntNode(63, null);size = 0;}public SLList(int x) {sentinel = new IntNode(63, null);sentinel.next = new IntNode(x, null);size = 1;}/** Adds x to the front of the list. */public void addFirst(int x) {sentinel.next = new IntNode(x, sentinel.next);size = size + 1;}/** Returns the first item in the list. */public int getFirst() {return sentinel.next.item;}/** Adds x to the end of the list. */public void addLast(int x) {size = size + 1; IntNode p = sentinel;/* Advance p to the end of the list. */while (p.next != null) {p = p.next;}p.next = new IntNode(x, null);}/** Returns the size of the list. */public int size() {return size;}public static void main(String[] args) {/* Creates a list of one integer, namely 10 */SLList L = new SLList();L.addLast(20);System.out.println(L.size());}
}3 DLList(LinkedListDeque链表双边队列)
/*** Created by JianjunChen on 08/16/2020* This is a Linked List Doubly ended queue Data Structure using Lists!* @Rule The amount of memory that your program uses at any given time must be* proportional to the number of items.* @Rule Do not maintain references to items that are no longer in the deque.* @Rule Implement all the methods listed above in “The Deque API” section.*/public class LinkedListDeque<T> {/**LinkedNode Nested Class*/private class LinkedNode {private LinkedNode prev; /* Doubly Linked List*/private T item;private LinkedNode next;public LinkedNode(LinkedNode p, T i, LinkedNode n) {prev = p;item = i;next = n;}}private LinkedNode sentinel;//private LinkedNode last;private int size;/** Constructor of LinkedListDeque */public LinkedListDeque() {sentinel = new LinkedNode(null, null, null);sentinel.prev = sentinel;sentinel.next = sentinel;//last = sentinel;size = 0;}/** Adds an item of type T to the front of the deque.*/public void addFirst(T item) {LinkedNode first = new LinkedNode(sentinel, item, sentinel.next);/* Note that the order cannot be reversed since if we firstly write* sentinel.next = first; the sentinel.next.prev will equal to first.prev!!!!*/sentinel.next.prev = first;sentinel.next = first;size += 1;}/** Adds an item of type T to the back of the deque. */public void addLast(T item) {LinkedNode last = new LinkedNode(sentinel.prev, item, sentinel);/* Note that the order cannot be reversed!!! */sentinel.prev.next = last;sentinel.prev = last;size += 1;}/** Returns true if deque is empty, false otherwise. */public boolean isEmpty() {if (sentinel.next == sentinel) {return true;}return false;}/** Returns the number of items in the deque. */public int size() {return size;}/* Prints the items in the deque from first to last, separated by a space. */public void printDeque() {LinkedNode p = sentinel;while (p.next != sentinel) {System.out.print(p.next.item + " ");p = p.next;}}/** Removes and returns the item at the front of the deque.If no such item exists, returns null.*/public T removeFirst() {if (isEmpty()) {return null;}T firstItem = sentinel.next.item;/* Note that the order cannot be reversed!!!*/sentinel.next.next.prev = sentinel;sentinel.next = sentinel.next.next;size -= 1;return firstItem;}/** Removes and returns the item at the back of the deque.* If no such item exists, returns null. */public T removeLast() {if (isEmpty()) {return null;}T lastItem = sentinel.prev.item;/* Note that the order cannot be reversed!!! */sentinel.prev.prev.next = sentinel;sentinel.prev = sentinel.prev.prev;size -= 1;return lastItem;}/** Gets the item at the given index, where 0 is the front, 1 is the next item,* and so forth. If no such item exists, returns null. Must not alter the deque! */public T get(int index) {if (index > size - 1) {return null;}LinkedNode p = sentinel.next;int i = 0;while (i != index) {p = p.next;i += 1;}return p.item;}/** Helper method for getRecursive */private T getRecursiveHelper(LinkedNode currentNode, int index) {if (index == 0) {return currentNode.item;}return getRecursiveHelper(currentNode.next, index - 1);}/** Same as get but using recursion!! */public T getRecursive(int index) {if (index > size - 1) {return null;}return getRecursiveHelper(sentinel.next, index);}
}4 AList(ArrayDeque数组双边队列)
/*** Created by JianjunChen on 08/18/2020* This is a Array based Doubly Ended Queue Data Structure!!* @Rule The starting size of your array should be 8.* @Rule Implement all the methods listed above in “The Deque API” section.* @Rule The amount of memory that at any given time must be proportional to the number* of items. For arrays of length 16 or more, your usage factor should always be at least 25%.**/// Circular ArrayDeque
public class ArrayDeque<T> {private int initialCapacity = 8; //initial array capacityprivate int capacity; //current array capacityprivate int eFactor = 2; //expanding factorprivate double usageFactor;private int mCapacity = 16; // The minimum capacity for contractionprivate double mRatio = 0.25; //The minimum usage ratio before contractionprivate int cFactor = 2; //contraction factorprivate T[] items;private int size;private int nextFirst;private int nextLast;public ArrayDeque() {capacity = initialCapacity;items = (T[]) new Object[initialCapacity];size = 0;nextFirst = 4;nextLast = 5;}/** Finding the next nextFirst and nextLast index in circle ArrayDeque. */private int oneMinus(int index) {if (index == 0) { // whether the index is out of bounds!index = capacity - 1;} else {index -= 1;}return index;}private int onePlus(int index) {if (index == capacity - 1) { // whether the index is out of bounds!index = 0;} else {index += 1;}return index;}/** Resize the original array to a new array with given capacity. */private void resize(int newCapacity) {T[] a = (T[]) new Object[newCapacity];int currentFirst = onePlus(nextFirst);int currentLast = oneMinus(nextLast);if (currentFirst < currentLast) {int length = currentLast - currentFirst + 1;System.arraycopy(items, currentFirst, a, 0, length);nextFirst = newCapacity - 1;nextLast = length;} else {int firstRightCount = capacity - currentFirst;int firstLeftCount = capacity - firstRightCount;System.arraycopy(items, currentFirst, a, 0, firstRightCount);System.arraycopy(items, 0, a, firstRightCount, firstLeftCount);nextFirst = newCapacity - 1;nextLast = capacity;}capacity = newCapacity;items = a;}/** Adds an item of type T to the front of the deque.* @Rule Must take constant time, except during resizing operations.*/public void addFirst(T item) {items[nextFirst] = item;size += 1;nextFirst = oneMinus(nextFirst);//The array is full, needed resize operation!if (size == capacity) {resize(size * eFactor);}}/** Adds an item of type T to the back of the deque.* @Rule Must take constant time, except during resizing operations.*/public void addLast(T item) {items[nextLast] = item;size += 1;nextLast = onePlus(nextLast);//The array is full, needed resize operation!if (size == capacity) {resize(size * eFactor);/*此处原为+1*/}}/** Returns true if deque is empty, false otherwise. */public boolean isEmpty() {if (size == 0) {return true;}return false;}/** Returns the number of items in the deque. */public int size() {return size;}/** Prints the items in the deque from first to last, separated by a space. */public void printDeque() {if (isEmpty()) {return;}int index = onePlus(nextFirst);while (index != nextLast) {System.out.print(items[index] + " ");index = onePlus(index);}}private void contract() {usageFactor = (double) size / capacity;if (usageFactor <= mRatio && capacity >= mCapacity) {int newCapacity = capacity / cFactor;resize(newCapacity);}}/** Removes and returns the item at the back of the deque. If no such item exists, returns null.* @Rule must take constant time, except during resizing operations.*/public T removeFirst() {if (isEmpty()) {return null;}int currentFirst = onePlus(nextFirst);T currentFirstItem = items[currentFirst];nextFirst = currentFirst;items[nextFirst] = null;size -= 1;contract();return currentFirstItem;}/** Removes and returns the item at the back of the deque. If no such item* exists, returns null..* @Rule must take constant time, except during resizing operations.*/public T removeLast() {if (isEmpty()) {return null;}int currentLast = oneMinus(nextLast);T currentLastItem = items[currentLast];nextLast = currentLast;items[nextLast] = null;size -= 1;return currentLastItem;}/*** Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth.* If no such item exists, returns null. Must not alter the deque!* @Rule must take constant time.*/public T get(int index) {if (index >= size) {return null;}int indexFromFirst = nextFirst + 1 + index;if (indexFromFirst >= capacity) {indexFromFirst -= capacity;}return items[indexFromFirst];}
}
C、203
100+101+....+999+1000=495550，大概500000
这张图片展示SLList代表Single-Linked List（单向链表），而ALList代表Array-Backed List（数组支持链表）的区别，即O(N)和O(NlogN)存疑
为了让alist更加通用实现了如下变化
/* Array based list.
@author Josh Hug*/
// 0 1 2 3 4 5 6 7
//items:[ 6 9 -1 2 0 0 0 0]
//size:5
/*Invariants:addlast:The next item we want to add,will go into position sizegetlast:The item we want to return is in position size -1size:The number of items in the list should be size.
*/
public class AList<Item> {private Item[] items;private int size;/*** Creates an empty list.*/public AList() {items = (Item[]) new Object[100];size = 0;}/*Resizes the underlying array to the target capacity.*/private void resize(int capacity) {Item[] a = (Item[]) new object[capacity];System.arraycopy(items, 0, a, 0, size);items = a;}/*Inserts x into the back of the list.*/public void addLast(Item x) {if (size == items.length) {resize(size + 1);}items[size] = x;size = size + 1;}/*Returns the item from the back of the List.*/public Item getlast() {return items[size - 1];}/*Gets the ith item in the list (0 is the front).*/public Item get(int i) {return items[i];}/*Returns the number of items in the list.*/public int size() {return size;}/*Deletes item from back of the list and returns deleted item.*/public Item removeLast() {Item x = getLast();items[size - 1] = null;size = size - 1;return x;}
}
