使用链接列表实现优先级队列

我已经使用链表实现了优先级队列。 在此优先级队列中，最小的int值具有最高值，因此通过调用remove方法将删除最小的方法。

节点类代码

public class Node { public int iData; public Node next; public Node(int x) { iData = x; } public void displayNode() { System.out.println(iData + " "); } } 

链接列表代码

 public class LinkList { private Node first; public LinkList() { first = null; } public boolean isEmpty() { return first == null; } public void insert(int x) { Node newNode = new Node(x); Node previous = null; Node current = first; while (current != null && x < current.iData) { previous = current; current = current.next; } if (previous == null) { newNode.next = first; first = newNode; } else { previous.next = newNode; newNode.next = current; } } public Node remove() { Node previous = null; Node current = first; Node temp = current; while (current.next != null) { previous = current; current = current.next; } previous.next = null; return temp; } public void display() { Node current = first; while (current != null) { current.displayNode(); current = current.next; } System.out.println(" "); } } 

优先级队列代码

 public class PriorityQ { private LinkList list; public PriorityQ() { list = new LinkList(); } public void insert(int x) { list.insert(x); } public void remove() { list.remove(); } public void displayList() { System.out.println("Largest Value to Smallest"); list.display(); } } 

它目前工作正常，但我不确定链接列表类中的remove方法是否是删除元素的最佳方法。 所以我在寻找建议。

Answer 1

remove()应该从列表中删除第一个元素，对吧？ 为什么要为此循环任何东西？

由于您的列表是单链接的（仅指向节点中的下一个元素），您需要做的就是：

1. 将first一个存储在一个临时变量中（如果它是！= null）

2. 然后first更新以指向列表中的第二项（ first.next if！= null）

3. 然后返回临时变量。

Answer 2

这可以通过具有指向第一节点的单个指针并通过将最小元素存储到第一节点来维持顺序来实现。

 public class LinkedListBasedOrderedMinPQ> implements PriorityQueue { private Node head; private int size; //Maintains an ordered linked list with the min element as the head @Override public void insert(T item) { Node node = head; head = insert(node, item); } private Node insert(Node node, T item) { Node newNode = createNewNode(item); if(null == node) { return newNode; } if(node.data.compareTo(item) > 0) { newNode.next = node; node = newNode; } else { node.next = insert(node.next, item); } return node; } private Node createNewNode(T item) { size++; return new Node(item); } @Override public T remove() { if(null == head) { return null; } T data = head.data; head = head.next; size--; return data; } @Override public int size() { return size; } private static class Node { private final T data; private Node next; public Node(T data) { this.data = data; } @Override public String toString() { return "Node [data=" + data + ", next=" + next + "]"; } } }