在Java创建自己的LinkedList类

Question

好吧，所以我试图在Java创建自己的LinkedList类（带有泛型类型），但是遇到了一些问题。我创建了一个LinkedListNode类，它基本上设置并获取next和right指针以及节点的键。我的LinkedList类代码发布在下面，如果您编译并运行，您会发现它没有按照应该的方式设置列表。此刻，我正在尝试在节点x之后插入节点y，但我的打印输出看起来像：

键：5-上一键：6-下一键：6键：6-上一键：null-下一键：null

我的代码：

public class LinkedList<T> {

    private LinkedListNode<T> m_head = null;
    private LinkedListNode<T> m_tail = null;

    public LinkedList() {
        m_head = new LinkedListNode<T>();
        m_tail = new LinkedListNode<T>();
        m_head.setNext(m_tail);
        m_tail.setPrev(m_head);
    }

    public LinkedListNode<T> getHead() {
        return m_head;
    }

    public LinkedListNode<T> getTail() {
        return m_tail;
    }

    public void insert(LinkedListNode<T> node, LinkedListNode<T> prev_node) {
        prev_node.getNext().setPrev(node);
        node.setPrev(prev_node);
        node.setNext(prev_node.getNext());
        prev_node.setNext(node);
    }

    public void delete(LinkedListNode<T> node) {

    }

    @Override
    public String toString() {
        LinkedListNode<T> pointer = m_head.getNext();
        String result = "";
        while(pointer.getKey() != null) {
            T prev_key = pointer.getPrev() == null ? null : pointer.getPrev().getKey();
            T next_key = pointer.getNext() == null ? null : pointer.getNext().getKey();
            result += "\nKey: " + pointer.getKey() + " - prev key: " + prev_key + " - next key: " + next_key;
            pointer = pointer.getNext();
        }
        return result;
    }

    public static void main(String[] args) {
        LinkedListNode<Integer> x = new LinkedListNode<Integer>(5);
        LinkedListNode<Integer> y = new LinkedListNode<Integer>(6);
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.insert(x, list.getHead());
        list.insert(y, x);
        System.out.println(list.toString());
    }

}

linkedListNode.java：

public class LinkedListNode<T> {

    private T m_key;
    private LinkedListNode<T> m_next = null;
    private LinkedListNode<T> m_prev = null;

    public LinkedListNode() {

    }

    public LinkedListNode(T key) {
        m_key = key;
    }

    public T getKey() {
        return m_key;
    }

    public void setKey(T key) {
        m_key = key;
    }

    public LinkedListNode<T> getNext() {
        return m_next;
    }

    public LinkedListNode<T> getPrev() {
        return m_next;
    }

    public void setNext(LinkedListNode<T> node) {
        m_next = node;
    }

    public void setPrev(LinkedListNode<T> node) {
        m_prev = node;
    }

}

Answer 1

您尝试实现的是双链表（如您有next和previous一样的双链表）。

而且你的结构设计有问题，保持头部和尾部可以问题的倾向。

您应该尝试使用引用其他元素的单个元素来实现它。

LinkedListNode<T> header = new LinkedListNode<T>(); 

header.getNext(); // head
header.getPrevious()//tail 

insert的示例

 public void insert(T element) { //We add to the begin

     LinkedListNode<T> newElement = LinkedListNode<T>(element);

     newElement.setNext(header); //previous begin we set to be next
     newElement.setPrevious(header.getPrevious()); //previous end we set to be end. 

     newElement.getPrevious().setNext(newElement); //to previous end we set new begin.
     newElement.getNext().setPrevious(newElement); //to previous begin we set new end. 

 }