索引前单链表插入

Question

我有两个 classes，DataStructure 和 LinkedList。我的DataStructure class 负责Linked List的插入/删除/替换/更新/显示。我在 linked 列表中的索引元素之前插入一个元素时遇到问题。当我调试代码并查看 LinkedList class 时，很明显 link 中断并且不连续。我不确定代码中有什么问题，因为它看起来合乎逻辑。如果有人能看到这个并指导我正确的方向，我将不胜感激。

这只是整个项目的一小部分，请随意更改类型

数据结构class:

public class DataStructure {
    //Item LinkedList field
    private LinkedList<Item> itemLinkedList;

    //Constructor
    public DataStructure() {
        itemLinkedList = new LinkedList<>();
    }

    //Add Item
    public boolean addItem(Item item) {
        boolean returnVal = false;
        if (item != null) {
            itemLinkedList.Move(2);
            itemLinkedList.Add(item);
            returnVal = true;
        }
        return returnVal;
    }
}

链表class

public class LinkedList<T> {
    //Fields
    private Node<T> Head;
    private Node<T> Current;
    private Node<T> Tail;
    private int size;

    //Constructor
    public LinkedList() {

    }

    //Methods
    private void AddHead(T data) {
        Node<T> temp = new Node<>(data);
        Tail = Current = Head = temp;
    }

    public void Add(T data) {
        if (data == null) throw new NullPointerException();
        else {
            Node<T> temp = new Node<>(data);
            if (Head == null) AddHead(data);
            else {
                if (Current == Tail) {
                    Tail.setNext(temp);
                    Current = Tail = temp;
                } else if (Current == Head) {
                    temp.setNext(Head);
                    Current = Head = temp;
                } else {
                    Node<T> cu = Current;
                    Current = temp;
                    Current.setNext(cu);
                }
            }
            size++;
        }
    }

    public Node MoveNext() {
        if (Current.getNext() != null)
            return Current = Current.Next;
        else return Current;
    }

    public void MoveLast() {
        if (Tail != null)
            Current = Tail;
    }

    public void MoveFirst() {
        if (Head != null)
            Current = Head;

    }

    public void Move(int index) {
        if (index >= size) MoveLast();
        else {
            MoveFirst();
            for (int i = 0; i < index; i++) MoveNext();
        }
    }

    class Node<T> {
        private T data;
        private Node<T> Next;

        public Node(T data, Node<T> next) {
            this.data = data;
            this.Next = next;
        }

        public Node(T data) {
            this.data = data;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node<T> getNext() {
            return Next;
        }

        public void setNext(Node<T> next) {
            Next = next;
        }

        public boolean hasNext() {
            return Next != null;
        }
    }
}

Answer 1

我观察到 LinkedList class 中的 Add() 方法存在问题。以下是修改后的版本：请尝试一次。还有一件事，在 Move(int index) 方法中，循环应该运行 for (index -1) 次，否则你将无法 link 之前的 link.

所以请尝试一下修改后的方法，如果问题仍然没有解决请告诉我：

  public void Move(int index) {
        if (index >= size) MoveLast();
        else {
            MoveFirst();
            for (int i = 0; i < index-1; i++) MoveNext();  //Run loop until (index - 1) so that you can have reference at the node no. 2 (in case of index 2)
        }
    }

 public void Add(T data) {
        if (data == null) throw new NullPointerException();
        else {
            Node<T> temp = new Node<>(data);
            if (Head == null) AddHead(data);
            else {
                if (Current == Tail) {
                    Tail.setNext(temp);
                    Current = Tail = temp;
                } else if (Current == Head) {
                    temp.setNext(Head);
                    Current = Head = temp;
                } else {
                    Node<T> cu = Current.getNext();
                    Current.setNext(temp);
                    temp.setNext(cu);
                    Current = cu; //Recently added node
                }
            }
            size++;
        }
    }

索引前单链表插入

Singly-linked List Insertion Before Index

java

linked-list

singly-linked-list