sorting - 如何在链表的 add 方法中对节点进行排序？

Question

//Node Class
public class MyNode<T extends Comparable<T>> implements INode<T> {
    public T key;
    public MyNode next;

    public MyNode(T key) {
        this.key = key;
        this.next = null;
    }
    @Override
    public T getKey() {
        return key;
    }

    @Override
    public void setKey(T key) {
        this.key = key;
    }

    @Override
    public INode getNext() {
        return next;
    }

    @Override
    public void setNext(INode next) {
        this.next = (MyNode) next;
    }

    @Override
    public int compareTo(INode<T> o) {
        return this.getKey().compareTo(o.getKey());
    }
}

public interface INode<T> {
    T getKey();
    void setKey(T key);
    INode<T> getNext();
    void setNext(INode next);

}

//Linked List Logic 
public class LinkedList<T> {
    public INode head;
    public INode tail;

    public LinkedList() {
        this.head = null;
        this.head = null;
    }


    public void addToLinkedListTest(INode newNode) {
        if (head == null) {
            this.head = newNode;
        }
        if (tail == null) {
            this.tail = newNode;
        } else {
            INode temp = this.head;
            this.head = newNode;
            this.head.setNext(temp);
        }
    }


    public void popLastElement() {
        if (head != tail) {
            INode temp = head;
            while (temp.getNext() != tail) {
                temp = temp.getNext();
            }

            this.tail = temp;
            INode tempOne = temp.getNext();
            tempOne = null;
        }
    }

    public void appendToLinkedList(INode newNode) {
        if (head == null) {
            this.head = newNode;
        }
        if (tail == null) {
            this.tail = newNode;
        } else {
            this.tail.setNext(newNode);
            this.tail = newNode;
        }
    }

    public void insertToLinkedList(INode beforeNode, INode afterNode, INode newNode) {
        INode temp = beforeNode.getNext();
        beforeNode.setNext(newNode);
        newNode.setNext(afterNode);
    }

    public void popFirstElement() {
        this.head = this.head.getNext();
    }

    public void printLinkedList() {
        StringBuffer allNodes = new StringBuffer();
        INode temp = head;
        while (temp.getNext() != null) {
            allNodes.append(temp.getKey());
            if (!temp.equals(tail))
                allNodes.append("->");
            temp = temp.getNext();
        }
        allNodes.append(temp.getKey());
        System.out.println(allNodes);
    }

    public T searchUsingKey(T key) {
        INode temp = head;
        while (temp.getNext() != null) {
            if (temp.getKey().equals(key)) {
                System.out.println("Found");
            }
            temp = temp.getNext();
        }
        return key;
    }

    public void searchUsingKeyInsert(T key, INode newNode) {
        INode temp = head;
        INode tempAfter;
        while (temp.getNext() != null) {
            if (temp.getKey().equals(key)) {
                System.out.println("Found");
                tempAfter = temp.getNext();
                insertToLinkedList(temp, tempAfter, newNode);
            }
            temp = temp.getNext();
        }

    }

    public void deleteUsingKey(T key) {
        INode temp = head;
        INode tempAfter;
        while (temp.getNext() != null) {
            if (temp.getNext().getKey().equals(key)) {
                tempAfter = temp.getNext().getNext();
                temp.setNext(tempAfter);
                break;
            }
            temp = temp.getNext();

        }

    }

    public void printAfterPopLast() {
        StringBuffer allNodes = new StringBuffer();
        INode temp = head;
        while (temp.getNext() != null) {
            allNodes.append(temp.getKey());
            if (!temp.equals(tail))
                allNodes.append("->");
            temp = temp.getNext();
        }
        System.out.println(allNodes);
    }

}

//我尝试使用比较器和可比较来比较节点，但它们都不起作用，或者我可能在实现上出错了 需要在将元素添加到具有通用类型 T 的链表时进行排序。甚至在插入后排序会帮助我解决问题的一部分。不确定在 Node 类或链表逻辑类中使用 compareTo 方法的位置。

标签： sortinggenericscomparatorsingly-linked-listcomparable

Answer 1

我建议进行以下更改以支持addSorted().LinkedList

• LinkedList 的类型参数需要更改为class LinkedList<T extends Comparable<? super T>>. 参考this使用? super T。
• INode将签名更改为interface INode<T, S extends<T>>. 这将避免在子类中进行强制转换。
• 最好制作MyNode内部类，LinkedList以便共享外部类的类型参数。

资源：

INode 变化：

interface INode<T, S extends INode<T, S>> {
    // ...
    void setNext(S next);
}

链表变化：

public class LinkedList<T extends Comparable<? super T>> {

    public MyNode head;

    public LinkedList() {
        this.head = null;
    }

    public void addSorted(MyNode newNode) {
        if (this.head == null) {
            this.head = newNode;
            return;
        }
        if (head.getKey().compareTo(newNode.getKey()) > 0) {
            newNode.next = head;
            this.head = newNode;
            return;
        }
        MyNode prev = head, cur;
        while ((cur = prev.next) != null && cur.getKey()
                                               .compareTo(newNode.getKey()) < 0) {
            prev = cur;
        }
        prev.next = newNode;
    }

    class MyNode implements INode<T, MyNode> {
        //...
        @Override
        public void setNext(MyNode next) {
        }
    }
}