优先级队列通过单链表插入实现

Question

我正在使用通用链表来实现优先级队列，其中我使用可比较的函数进行插入函数，它找到一个大小大于当前节点的插槽。我实际上在让添加函数根据优先级队列要求插入元素时遇到问题。优先级队列应从小到大。

编辑：我意识到问题在于插入一个比头部大的数字。在添加 11 期间，该函数仅与 5 进行比较，并将其添加到 5 之后，这会破坏序列。

电流输出

PQ: 5
PQ: 5,10 
PQ: 5,9,10
PQ: 5,11,9,10
PQ: 5,7,11,9,10
PQ: 2,5,7,11,9,10

期望的输出

PQ: 2,5,7,9,10,11

我的添加函数

public class PQLinkedList<T extends Comparable<T>>{
private class Node{
private T data;
private Node next;

// Constructor that takes in data to input for the node
public Node(T data) {
this.data = data;
this.next = null;
}
}

private int length = 0;
private Node head;
int cmp = 0;
public PQLinkedList() {
head = null;
}
//Compare with each element till it finds a suitable position to insert itself
//Ascending order
//INCOMPLETE
//Compare part of this code is not complete!
public void addPQ( T data) {
Node node = new Node(data);
Node temp2 = null;
if ( head == null) {
addFirst(data);
}
else {
Node curr = head;
int count = getSize();

while ( count != 0) {    
cmp = data.compareTo(curr.data);

if ( cmp < 0 ) {
addFirst(data);
break;
}
else if (cmp>=0 ){         
if ( curr.next == null) {
curr.next = node;
break;
}
// if there curr.next is not empty
// Move all the nodes towards to tail by 1
else {
// after = one space after pos
// PROBLEM
temp2 = curr.next;
Node after = curr.next;
while( after != null) {
after = after.next;
}
node.next = temp2;    
curr.next = node;
break;
}

}

else {
curr = curr.next;
}
count--;
}
}
length++;
}


private void addFirst(T data) {
Node node = new Node(data);
if ( head == null ) {
head = node;
}
else {
Node temp = head;
head = node;
node.next = temp;
}
length++;
}
//TO-DO
public void remove( T data) {
if ( !search(data)) {
System.out.println("Linked list does not contain that element!");
return;
}
else if ( head.data == data) {
head = head.next;
}
else {
// If curr is the node to be deleted.
// link from previous node to curr, link from curr to next node
//Traverse through the linkedlist till it finds the node to be deleted and skip it
Node curr = head;
while ( curr != null & curr.next != null ) {
if ( curr.next.data == data) {
//Check if the node 2 next after curr is null
//if so, remove curr.next which contains the value that we want to delete
if ( curr.next.next != null) {
curr.next = curr.next.next;
}
//curr.next.next is null so just curr.next which contains the value we want to delete
else {
curr.next = null;
}
}
//Traverse the curr node
else {
curr = curr.next;
}
}
length--;
}
}

// Retrieves and removes the head of the priority queue
public T poll() {
if ( isEmpty()) {
System.out.println("Linked list is empty!");
return null;
}
else {
Node temp = null;
temp = head ;
head = head.next;
length--;
return temp.data;
}
}
// Retrieves the head of the priority queue
public T peek() {
if ( isEmpty()) {
System.out.println("Linked list is empty!");
return null;
}
else {
return head.data;
}
}
public void clear() {
Node curr = head;
while ( curr != null) {
curr = curr.next;
}
}

public int getSize() {
return length;
}

public boolean search(T data) {
if ( isEmpty()) {
System.out.println("Linked list is empty!");
return false;
}
else {
Node node = head;
while ( node != null ) {
if ( node.data == data) {
return true;
}
node = node.next;
}
return false;
}
}

public boolean isEmpty() {
if ( length == 0) {
return true;
}
return false;
}
@Override
public String toString() {
String str = "PQ: ";
Node node = head;
while ( node != null) {
str = str + node.data;
if ( node.next != null) {
str = str + ",";
}
node = node.next;
}
return str;
}

}

我的主要

public class priorityQueueImplementation {
public static void main(String[] args) {
PQLinkedList<Integer> test = new PQLinkedList<Integer>();
test.add(5);
test.add(10);
test.add(9);
test.add(11);
test.add(7);
test.add(2);
System.out.println( test.toString());

}
}

Answer 1

由于这是一个单向链表，我们不能将节点添加到前一个节点。我们只能添加到后续节点。在节点插入过程中，我们需要将data与列表进行比较。每个节点一个，有 5 种情况：

1. current为空，data成为新头
2. data比current小，data成为新的头
3. data大于current，data小于next。在current和next之间插入data
4. data大于current，next为空。在current后插入data
5. data大于current，data大于next。等待下一次迭代

public void addPQ(T data) {
Node node = new Node(data);
Node curr = head;
if (head == null) {
// current is null, data become the new head
addFirst(data);
} else {
while (curr != null) {
int cmpLeft = data.compareTo(curr.data);
if (cmpLeft < 0) {
// data is smaller than current, `data` become the new head
addFirst(data);
break;
} else {
// data is greater than current
if (curr.next == null) {
// next is null. Insert `data` after `current`
addAfter(curr, node);
break;
} else {
int cmpRight = data.compareTo(curr.next.data);
if (cmpRight < 0) {
// data is smaller then next. Insert data between current and next
addAfter(curr, node);
break;
}
}
// data is greater then next. Wait for next iteration
curr = curr.next;
}
}
}
}
private void addAfter(Node currNode, Node newNode) {
if (currNode == null) {
currNode = newNode;
} else {
Node tempTail = currNode.next;
currNode.next = newNode;
newNode.next = tempTail;
}
length++;
}

输出

PQ: 2,5,7,9,10,11