java - Java排序中的链表实现不起作用

Question

我创建了自己的链表。我想使用 Collections.sort 方法对链接列表进行排序。所以我将 MyLinkedList 类扩展为 java.util.LinkedList。我还创建了 Comparator 和 Comparable 实现。但两者都不起作用。请找到下面的代码。

//链表实现。

package com.java.dsa;

class Node<E> {
    E data;
    Node<E> nextLink;
    public Node(E data) {
        this.data = data;
    }
}

public class MyLinkedList<E> extends java.util.LinkedList<E>{

    private static final long serialVersionUID = 1L;
    private Node<E> firstNodePointer;
    private Node<E> nodePointer;

    public boolean isEmpty() {
        return nodePointer == null;
    }

    public boolean add(E data) {
        super.add(data);

        Node<E> node = new Node<E>(data);

        if (firstNodePointer == null) {
            firstNodePointer = node;
            nodePointer = node;
        }else{
            nodePointer.nextLink = node;
        }
        nodePointer = node;
        return true;
    }

    public boolean remove(Object data){
        super.remove(data);

        Node<E> counterNodePointer = firstNodePointer;
        Node<E> tempNodePointer = firstNodePointer;

        while (counterNodePointer != null && !counterNodePointer.data.equals(data)) {
            tempNodePointer = counterNodePointer;
            counterNodePointer = counterNodePointer.nextLink;
        }
        if(tempNodePointer.equals(firstNodePointer)){
            firstNodePointer = firstNodePointer.nextLink;
            return true;
        }
        else if(counterNodePointer != null && tempNodePointer != null){
            tempNodePointer.nextLink = counterNodePointer.nextLink;
            return true;
        }
        return false;
    }

    public void printList() {
        Node<E> counterNodePointer = firstNodePointer;
        while (counterNodePointer != null) {
            System.out.println(counterNodePointer.data);
            counterNodePointer = counterNodePointer.nextLink;
        }
    }
}

//测试链表

package com.java.dsa;

import java.util.Collections;
import java.util.Comparator;

//员工类

class Employee implements Comparable<Employee> {
    private String name;
    private int id;

    public Employee(String name, int id) {
        super();
        this.name = name;
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    @Override
    public String toString() {
        return this.name + " " + this.id;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + id;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Employee other = (Employee) obj;
        if (id != other.id)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    @Override
    public int compareTo(Employee employee) {
        return this.id - employee.id;
    }
}

class EmployeeSort implements Comparator<Employee> {

    @Override
    public int compare(Employee emp1, Employee emp2) {

        if (emp2.getId() - emp1.getId() > 0)
            return 1;
        else
            return -1;
    }
}

public class TestLinkedList {
    public static void main(String[] args) {
        MyLinkedList<Employee> myList = new MyLinkedList<Employee>();

        for (int i = 10; i > 0; i--) {
            Employee emp = new Employee("Sohan "+i, i);
            myList.add(emp);
        }
        myList.printList();
        Collections.sort(myList, new EmployeeSort());
        myList.printList();
    }
}

Answer 1

实际上它有效。只是您的内部数据结构没有由 Collections.sort() 更新，并且因为您断言该程序无法在 printList() 的输出上运行>，这依赖于该数据结构，您会看到元素的顺序保持不变。请改用此方法:

public void printParentDataStructure() {
  for ( E e : this ) System.out.println( e );
}

并查看您的比较器完美地完成其工作。所以你的问题是你有两个数据结构并且不保持它们同步。您的下一个问题可能是“我怎样才能使它们保持同步？” - 嗯，本质上您应该重写每个方法，并像您一样调用 super()在 add() 和 remove() 中执行。 不要这样做!这完全是无稽之谈。

很明显，您想要实现一个链表来学习数据结构，但也许您应该首先更好地了解 OOP 编程的基本原理。