什么使三端队列的 Java 链表实现变慢？
What makes the Java linked-list implementation of a triple-ended queue slow?
我正在解决 Kattis 问题 Teque，并且必须只用四个操作来实现一个 teque（三端队列）：推到前面、推到后面、推到中间（中值）和在索引处读取项目。这个作业的重点是时间复杂度，所以我使用了尾链表来方便地在前后添加元素。
对于 push-to-middle 函数，我没有在我的列表中调用 size()，而是在 Teque 中存储了一个 class 变量来跟踪列表中的元素数量。这启用了非常快速的查找。
class Teque {
public TailedLinkedList list;
public Kattio io = new Kattio(System.in, System.out);
public int numItems;
public Teque() {
this.list = new TailedLinkedList();
this.numItems = 0;
}
public void push_back(int x) {
numItems++;
list.addBack(x);
}
public void push_front(int x) {
numItems++;
list.addFront(x);
}
public void push_middle(int x) {
int median = (numItems + 1) / 2;
list.addAtIndex(median, x);
numItems++;
}
public int get(int i) {
int result = list.getItemAtIndex(i);
io.println(result);
io.flush();
return result;
}
}
TailedLinkedList 的实现：
import java.util.*;
class TailedLinkedList implements ListInterface {
// attributes
public ListNode head;
public ListNode tail;
public int num_nodes;
// interface methods
// Return true if list is empty; otherwise return false.
public boolean isEmpty() { return (num_nodes == 0); }
// Return number of items in list
public int size() { return num_nodes; }
// return index of item if item is found in the list, otherwise return -1
public int indexOf(int item) {
int index = 0;
for (ListNode cur = head; cur != null; cur = cur.getNext()) {
if (cur.getItem() == item)
return index;
else
index++;
}
return -1;
}
// return true if item is in the list false otherwise
public boolean contains(int item) {
if (indexOf(item) != -1)
return true;
return false;
}
// get item at index
public int getItemAtIndex(int index) {
int counter = 0;
int item = 0;
if (index < 0 || index > size()-1) {
System.out.println("invalid index");
System.exit(1);
}
if (index == size()-1)
item = tail.getItem();
else {
for (ListNode cur = head; cur != null; cur = cur.getNext()) {
if (counter == index) {
item = cur.getItem();
break;
}
counter++;
}
}
return item;
}
// Return first item
public int getFirst() { return getItemAtIndex(0); }
// Return last item
public int getLast() { return getItemAtIndex(size()-1); }
// add item at position index, shifting all current items from index onwards to the right by 1
// pre: 0 <= index <= size()
public void addAtIndex(int index, int item) {
ListNode cur;
ListNode newNode = new ListNode(item);
if (index >= 0 && index <= size()) {
if (index == 0) // insert in front
insert(null,newNode);
else if (index == size()) // insert at the back, don't have to move all the way to the back
insert(tail,newNode);
else {
cur = getNodeAtIndex(index-1); // access node at index-1
insert(cur,newNode);
}
}
else { // index out of bounds
System.out.println("invalid index");
System.exit(1);
}
}
// Add item to front of list
public void addFront(int item) { addAtIndex(0,item); }
// Add item to back of list
public void addBack(int item) { addAtIndex(size(),item); }
// remove item at index and return it
// pre: 0 <= index < size()
public int removeAtIndex(int index) {
ListNode cur;
int item = 0;
// index within bounds and list is not empty
if (index >= 0 && index < size() && head != null) {
if (index == 0) // remove 1st item
item = remove(null);
else {
cur = getNodeAtIndex(index-1); // access node at index-1
item = remove(cur);
}
}
else { // index out of bounds
System.out.println("invalid index or list is empty");
System.exit(1);
}
return item;
}
// Remove first node of list
public int removeFront() { return removeAtIndex(0); }
// Remove last node of list
public int removeBack() { return removeAtIndex(size()-1); }
// Print values of nodes in list.
public void print() {
if (head == null)
System.out.println("Nothing to print...");
else {
ListNode cur = head;
System.out.print("List is: " + cur.getItem());
for (int i=1; i < num_nodes; i++) {
cur = cur.getNext();
System.out.print(", " + cur.getItem());
}
System.out.println(".");
}
}
// non-interface helper methods
public ListNode getHead() { return head; }
public ListNode getTail() { return tail; }
/* return the ListNode at index */
public ListNode getNodeAtIndex(int index) {
int counter = 0;
ListNode node = null;
if (index < 0 || index > size()-1) {
System.out.println("invalid index");
System.exit(1);
}
if (index == size()-1) // return tail if index == size()-1
return tail;
for (ListNode cur = head; cur != null; cur = cur.getNext()) {
if (counter == index) {
node = cur;
break;
}
counter++;
}
return node;
}
// insert newNode after the node referenced by cur
public void insert(ListNode cur, ListNode n) {
// insert in front
if (cur == null) {
n.setNext(head);
head = n; // update head
if (tail == null) // update tail if list originally empty
tail = head;
}
else { // insert anywhere else
n.setNext(cur.getNext());
cur.setNext(n);
if (cur == tail) // update tail if inserted new last item
tail = tail.getNext();
}
num_nodes++;
}
// remove the node referenced by cur.next, and return the item in the node
// if cur == null, remove the first node
public int remove(ListNode cur) {
int value;
if (cur == null) { // remove 1st node
value = head.getItem();
head = head.getNext(); // update head
if (num_nodes == 1) // update tail to null if only item in list is removed
tail = null;
}
else { // remove any other node
value = cur.getNext().getItem();
cur.setNext(cur.getNext().getNext());
if (cur.getNext() == null) // update tail if last item is removed
tail = cur;
}
num_nodes--;
return value;
}
}
不过，我的代码还有运行秒超时（10万行输入，限时2秒）。是否有任何明显的地方可以改进我的算法？ addAtIndex 和 getItemAtIndex 运行 在 O(n) 时间内。
push_midle 导致遍历列表的一半。一个解决方案是使用两个列表，前半部分和后半部分。如果列表变得不平衡，则在两个列表之间移动元素。
（可能 ListIterator 也可能这样做；尽管对于一种天真的方法，必须担心 ConcurrentModificationException。）
Joop Eggen 的解决方案的修改是使用 2 个数组（前数组用于快速 pushFront，后数组用于快速 pushBack）。
- frontIndex = front.length / 2 和 front.length - 1
之间的任何值
- frontMidIndex = frontIndex - 1
- backIndex = 0 到 back.length / 2
之间的任何值
- backMidIndex = backIndex + 1
有效内容：front[frontIndex .. frontMidIndex[ + back[backMidIndex .. backIndex[
pushFront:
- frontIndex > 0？
- 置frontIndex，递减frontIndex
- else frontMidIndex < front.length
- 将 front 数组向后移动 x，将 frontIndex 和 frontMidIndex 增加 x，设置如上
- 其他
- 要么将某些部分复制到后面或增长数组，然后像上面那样继续
回击：
- 后退相同，backIndex (< back.length), backMidIndex (> 0)，切换in/decrement和移位方向
pushMid（这需要更多思考）：
- 最好前后有效长度相等或相差1。
然后这成为 frontMidIndex 或 backMidIndex 的集合（与上面的逻辑类似）
- 如果mid落在两个数组之一的有效范围的中间，则可以
- 移动此数组中的内容以为元素创建位置。
- 或在两个数组之间移动内容以调整 midIndexes 以进一步 pushMid。
我正在解决 Kattis 问题 Teque，并且必须只用四个操作来实现一个 teque（三端队列）：推到前面、推到后面、推到中间（中值）和在索引处读取项目。这个作业的重点是时间复杂度，所以我使用了尾链表来方便地在前后添加元素。
对于 push-to-middle 函数，我没有在我的列表中调用 size()，而是在 Teque 中存储了一个 class 变量来跟踪列表中的元素数量。这启用了非常快速的查找。
class Teque {
public TailedLinkedList list;
public Kattio io = new Kattio(System.in, System.out);
public int numItems;
public Teque() {
this.list = new TailedLinkedList();
this.numItems = 0;
}
public void push_back(int x) {
numItems++;
list.addBack(x);
}
public void push_front(int x) {
numItems++;
list.addFront(x);
}
public void push_middle(int x) {
int median = (numItems + 1) / 2;
list.addAtIndex(median, x);
numItems++;
}
public int get(int i) {
int result = list.getItemAtIndex(i);
io.println(result);
io.flush();
return result;
}
}
TailedLinkedList 的实现：
import java.util.*;
class TailedLinkedList implements ListInterface {
// attributes
public ListNode head;
public ListNode tail;
public int num_nodes;
// interface methods
// Return true if list is empty; otherwise return false.
public boolean isEmpty() { return (num_nodes == 0); }
// Return number of items in list
public int size() { return num_nodes; }
// return index of item if item is found in the list, otherwise return -1
public int indexOf(int item) {
int index = 0;
for (ListNode cur = head; cur != null; cur = cur.getNext()) {
if (cur.getItem() == item)
return index;
else
index++;
}
return -1;
}
// return true if item is in the list false otherwise
public boolean contains(int item) {
if (indexOf(item) != -1)
return true;
return false;
}
// get item at index
public int getItemAtIndex(int index) {
int counter = 0;
int item = 0;
if (index < 0 || index > size()-1) {
System.out.println("invalid index");
System.exit(1);
}
if (index == size()-1)
item = tail.getItem();
else {
for (ListNode cur = head; cur != null; cur = cur.getNext()) {
if (counter == index) {
item = cur.getItem();
break;
}
counter++;
}
}
return item;
}
// Return first item
public int getFirst() { return getItemAtIndex(0); }
// Return last item
public int getLast() { return getItemAtIndex(size()-1); }
// add item at position index, shifting all current items from index onwards to the right by 1
// pre: 0 <= index <= size()
public void addAtIndex(int index, int item) {
ListNode cur;
ListNode newNode = new ListNode(item);
if (index >= 0 && index <= size()) {
if (index == 0) // insert in front
insert(null,newNode);
else if (index == size()) // insert at the back, don't have to move all the way to the back
insert(tail,newNode);
else {
cur = getNodeAtIndex(index-1); // access node at index-1
insert(cur,newNode);
}
}
else { // index out of bounds
System.out.println("invalid index");
System.exit(1);
}
}
// Add item to front of list
public void addFront(int item) { addAtIndex(0,item); }
// Add item to back of list
public void addBack(int item) { addAtIndex(size(),item); }
// remove item at index and return it
// pre: 0 <= index < size()
public int removeAtIndex(int index) {
ListNode cur;
int item = 0;
// index within bounds and list is not empty
if (index >= 0 && index < size() && head != null) {
if (index == 0) // remove 1st item
item = remove(null);
else {
cur = getNodeAtIndex(index-1); // access node at index-1
item = remove(cur);
}
}
else { // index out of bounds
System.out.println("invalid index or list is empty");
System.exit(1);
}
return item;
}
// Remove first node of list
public int removeFront() { return removeAtIndex(0); }
// Remove last node of list
public int removeBack() { return removeAtIndex(size()-1); }
// Print values of nodes in list.
public void print() {
if (head == null)
System.out.println("Nothing to print...");
else {
ListNode cur = head;
System.out.print("List is: " + cur.getItem());
for (int i=1; i < num_nodes; i++) {
cur = cur.getNext();
System.out.print(", " + cur.getItem());
}
System.out.println(".");
}
}
// non-interface helper methods
public ListNode getHead() { return head; }
public ListNode getTail() { return tail; }
/* return the ListNode at index */
public ListNode getNodeAtIndex(int index) {
int counter = 0;
ListNode node = null;
if (index < 0 || index > size()-1) {
System.out.println("invalid index");
System.exit(1);
}
if (index == size()-1) // return tail if index == size()-1
return tail;
for (ListNode cur = head; cur != null; cur = cur.getNext()) {
if (counter == index) {
node = cur;
break;
}
counter++;
}
return node;
}
// insert newNode after the node referenced by cur
public void insert(ListNode cur, ListNode n) {
// insert in front
if (cur == null) {
n.setNext(head);
head = n; // update head
if (tail == null) // update tail if list originally empty
tail = head;
}
else { // insert anywhere else
n.setNext(cur.getNext());
cur.setNext(n);
if (cur == tail) // update tail if inserted new last item
tail = tail.getNext();
}
num_nodes++;
}
// remove the node referenced by cur.next, and return the item in the node
// if cur == null, remove the first node
public int remove(ListNode cur) {
int value;
if (cur == null) { // remove 1st node
value = head.getItem();
head = head.getNext(); // update head
if (num_nodes == 1) // update tail to null if only item in list is removed
tail = null;
}
else { // remove any other node
value = cur.getNext().getItem();
cur.setNext(cur.getNext().getNext());
if (cur.getNext() == null) // update tail if last item is removed
tail = cur;
}
num_nodes--;
return value;
}
}
不过，我的代码还有运行秒超时（10万行输入，限时2秒）。是否有任何明显的地方可以改进我的算法？ addAtIndex 和 getItemAtIndex 运行 在 O(n) 时间内。
push_midle 导致遍历列表的一半。一个解决方案是使用两个列表，前半部分和后半部分。如果列表变得不平衡，则在两个列表之间移动元素。
（可能 ListIterator 也可能这样做；尽管对于一种天真的方法，必须担心 ConcurrentModificationException。）
Joop Eggen 的解决方案的修改是使用 2 个数组（前数组用于快速 pushFront，后数组用于快速 pushBack）。
- frontIndex = front.length / 2 和 front.length - 1 之间的任何值
- frontMidIndex = frontIndex - 1
- backIndex = 0 到 back.length / 2 之间的任何值
- backMidIndex = backIndex + 1
有效内容：front[frontIndex .. frontMidIndex[ + back[backMidIndex .. backIndex[
pushFront:
- frontIndex > 0？
- 置frontIndex，递减frontIndex
- else frontMidIndex < front.length
- 将 front 数组向后移动 x，将 frontIndex 和 frontMidIndex 增加 x，设置如上
- 其他
- 要么将某些部分复制到后面或增长数组，然后像上面那样继续
回击：
- 后退相同，backIndex (< back.length), backMidIndex (> 0)，切换in/decrement和移位方向
pushMid（这需要更多思考）：
- 最好前后有效长度相等或相差1。 然后这成为 frontMidIndex 或 backMidIndex 的集合（与上面的逻辑类似）
- 如果mid落在两个数组之一的有效范围的中间，则可以
- 移动此数组中的内容以为元素创建位置。
- 或在两个数组之间移动内容以调整 midIndexes 以进一步 pushMid。