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");
}
}
}
}

这是内部类课程节点：

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

有三种方法(假设index值为正)可以在链表中的索引处进行插入：

1. 在头部 (index == 0)
2. 尾巴后 (index >= currentSize)
3. 在中间 (在占用的索引处) (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);
}
}

Answer 2

首先在链接列表中，如果

索引<链接列表大小>

然后有一个对象已经在链接列表中。如果你在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
} 

希望这有帮助！