如何为自定义链表创建一些方法(例如:insertAtIndex())

Question

我是链表概念的新手，第一次构建这个自定义链表时遇到了很多麻烦。

我有两个类：CellPhone和CellList。

在CellPhone中，我有4个属性：serialNum(long(、brand(String(、year(int(和price(double(。

在CellList中，我有：

• 一个名为CellNode的内部类，它有两个属性：phone(CellPhone(和next(CellNode(
• 和两个属性head(CellNode(和size(int(

这来自我的CellList类：

private CellNode head; // point first node in this list object
private int size; // current size of the list(how many nodes in the list)
public CellList() {
head = null;
size = 0;
}
public CellList(CellList c) { // is this a correct deep copying?
head = new CellNode(c.head);
size = c.getSize();
}
public int getSize() {
return size;
}
public void addToStart(CellPhone c) {
head = new CellNode(c, null); //head.getPhone() = c, head.getNextNode() = null.
size++;
}

我甚至不确定addToStart方法是否正确，现在我需要添加像insertAt(/deleteFrom)Index(CellPhone c, int index)这样的方法。我一直做到这里：

public void insertAtIndex(CellPhone c, int index) { //index is invalid when it's not 0<index<size-1
if(index<0 || index>size-1) {
throw new NoSuchElementException("index is invalid! System terminated.");
}

但我不能完全理解Node是如何工作的，所以我被卡住了。

---

这是完整的代码：

import java.util.NoSuchElementException;
public class CellList {
class CellNode {
private CellPhone phone;
private CellNode next;
public CellNode() {
phone = null;
next = null;
}
public CellNode(CellPhone c, CellNode n) {
phone = c;
next = n;
}
public CellNode(CellNode c) {
this(c.getPhone(), c.getNextNode());
}
public CellNode clone() {
CellNode c = new CellNode(phone, next);
return c;
}
public CellPhone getPhone() {
return phone;
}
public CellNode getNextNode() {
return next;
}
public void setPhone(CellPhone c) {
phone = c;
}
public void setNextNode(CellNode n) {
next = n;
}
}
private CellNode head; // point first node in this list object
private int size; // current size of the list(how many nodes in list)
public CellList() {
head = null;
size = 0;
}
public CellList(CellList c) {
head = new CellNode(c.head);
size = c.getSize();
}
public int getSize() {
return size;
}
public void addToStart(CellPhone c) {
head = new CellNode(c, null); //head.getPhone() = c, head.getNextNode() = null.
size++;
}
public void insertAtIndex(CellPhone c, int index) { //index is invalid when it's not 0<index<size-1
if(index<0 || index>size-1) {
throw new NoSuchElementException("index is invalid! System terminated.");
}
}
public void showContents() {
while(head.getNextNode() != null) {
System.out.println(head.getPhone()+"---->");
head = head.getNextNode();
}
}
}

Answer 1

如果你想在索引x处插入一个节点，你必须，转到索引x-1处的节点，将节点x-1的下一个值存储在一个临时变量中，将要插入的节点放在x-1节点的下一属性中，并将临时变量中的值放在要插入节点的下个属性中。