【CS61B】链表IntList、SLList、DLList、AList整理
本文整理了CS61B中的链表IntList、SLList、DLList、AList实现。
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));
}
}
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 capacity
private int capacity; //current array capacity
private int eFactor = 2; //expanding factor
private double usageFactor;
private int mCapacity = 16; // The minimum capacity for contraction
private double mRatio = 0.25; //The minimum usage ratio before contraction
private int cFactor = 2; //contraction factor
private 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);
}
}
/** 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];
}
}
- 原文作者：jchen
- 原文链接：http://jchenTech.github.io/post/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/CS61B%E9%93%BE%E8%A1%A8IntListSLListDLListAList/
- 版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，非商业转载请注明出处（作者，原文链接），商业转载请联系作者获得授权。