Java LinkedList 在索引处插入对象

Question

我在理解如何在链接中放置对象时遇到一些麻烦。在这种情况下，如果在特定索引处已经有一个对象，它不会替换它（这是另一种方法）。我想我无法理解如何到达特定索引、从该索引检索数据，然后将数据放在那里并连接节点或告诉用户那里已经有一个对象。

这是我的代码：

public class CourseList {

    private Coursenode head;
    int currentSize;

    public void insertAtIndex(Course c, int index) {

        Coursenode insert =new Coursenode(c,head); 
        Coursenode temp = new Coursenode();

        if (index > currentSize - 1 || index < 0) {
            throw (new IndexOutOfBoundsException());
        }


        for(int x = 0; x < index; x++) {
            if (insert.getNext()!= null) {
                temp = insert;
                insert.setNext(insert);
                insert.setData(temp.getData());
            }
            if (insert.getNext() == null && x == index) {
                insert.setNext(insert.getNext());
            }
            if (insert.getNext() != null && x == index) {
                System.out.println("There is already a Course at that Index");
            }

        }
    }
}

这是内部 class 课程节点：

public class Coursenode {

    private Course data;
    private Coursenode next;

    public Coursenode() {
        this.data = null;
        this.next = null;
    }

    public Coursenode(Course course, Coursenode next) {
        this.data=course;
        this.next= next;
    }

    public Coursenode(Coursenode x) {
        this.data = x.getData();
        this.next = x.getNext();
    }

    public Course getData() {
        return data;
    }

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

    public Coursenode getNext() {
        return next;
    }

    public void setNext(Coursenode next) {
        this.next = next;
    }

    //Clone method
    public void clone(Coursenode new_cn){ 
         new_cn = new Coursenode (this.getData(),this.getNext());
    }
}

如有任何想法，我将不胜感激，我怀疑我在节点之间的头部引用中迷路了，但我不太清楚如何解决这个问题。

Answer 1

首先在链表中 if

index < linkedlistsize

那么链表中已经有一个对象。如果您在 node.next 中有一个空节点，那么您如何知道您已经到达链表的末尾。

public class CourseList {

    private Coursenode head;
    int currentSize;

    public void insertAtIndex(Course c, int index) {

        Coursenode insert =new Coursenode(c,head); 
        Coursenode temp = new Coursenode();

        if (index > currentSize - 1 || index < 0) {
            throw (new IndexOutOfBoundsException());
        }

        //tempnode = head;
        for(int x=1; x< index;x++) {
         //tempnode = tempnode.next;
        }
        //nodeatindex = tempnode;
        //you can get details of the node
}

希望对您有所帮助！

Answer 2

可以通过三种方式（假设正 index 值）在链表的索引处进行插入：

领先(index == 0)
后尾(index >= currentSize)
在中间（在占用的索引处）(index > 0 && index < currentSize)

可能会有人倾向于认为在尾部插入是另一种情况，但是后面我们会看到在尾部插入和在中间插入是一样的，因为尾部会向前滑动。

如果插入在头部，需要将插入节点的next设置为旧的head，然后将head设置为插入节点：

private void insertAtHead(Course course) {
    Coursenode insertedNode = new Coursenode(c, head);
    head = insertedNode;
}

如果插入发生在尾部之后，一种常见的处理方法是抛出某种异常，例如 IndexOutOfBoundsException:

throw new IndexOutOfBoundsException("Cannot insert course after the tail of the course list");

如果插入发生在占用的索引处，则现有节点（以及现有节点之后的所有节点）必须向前推进。这意味着插入节点的next必须设置为当前占用索引的节点，并且当前索引处节点的前一个节点的next必须设置为插入节点。本质上，插入的节点被融合到列表中。为此，必须遍历链表，直到找到被占用的节点：

private void insertAtOccupied(Course course, int index) {
    Coursenode previous = null;
    Coursenode current = head;

    for (int i = 1; i <= index; i++) {
        // Track the previous and current nodes
        //   previous = node at i - 1
        //   current = node at i
        previous = current;
        current = current.next;
    }

    Coursenode insertedNode = new Coursenode(c, current.next);
    previous.next = insertedNode;
}

将这些案例放在一起，我们可以创建以下逻辑：

public void insertAt(Course course, int index) {

    if (index == 0) {
        insertAtHead(course);
    }
    else if (index >= currentSize) {
        throw new IndexOutOfBoundsException("Cannot insert course after the tail of the course list");
    }
    else if (index > 0 && index < currentSize) {
        insertAtOccupied(course, index);
    }
}

Java LinkedList 在索引处插入对象

Java LinkedList inserting Object at index

java

methods

linked-list

inner-classes

singly-linked-list