1

我创建了自己的链表。我想使用 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();
    }
}
4

2 回答 2

0

java.util.LinkedList不是为子类化而设计的类，您的代码可能只是破坏了它的内部和不变量。

如果您想自己实现一个链表，但又想省去实现完整List接口的工作量，那么请使用AbstractList它作为您的基类。这个类的明确目的正是你想要做的。

于 2013-08-17T20:59:19.490 回答
0

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

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

并看到您的比较器完美地完成了它的工作。所以你的问题是你有两个数据结构并且不让它们保持同步。您的下一个问题可能是“我怎样才能让它们保持同步？” - 好吧，基本上你应该重写每一个方法，并super()像你在add()and中那样调用remove()。不要那样做！这完全是胡说八道。

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

于 2013-08-17T21:26:01.733 回答