英文:
Does singly linked list have to be defined recursively?
问题
我理解如何在Java中递归地定义单链表：
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
我的问题是：单链表必须以递归方式定义吗？
英文:
I understand how to define a singly linked list recursively in java:
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
My question is: Does singly linked list have to be defined recursively?
答案1
得分: 1
不，一点也不。这里只是实现链表的众多方法之一，非递归方式（方法的实现未展示）：
class LinkedList {
private ListNode[] nodes;
private int start;
private int nextEmpty;
private static class ListNode {
private int val;
private int next;
}
}
使用数组来存储节点。每个节点都有一个值和一个next。next字段存储数组中下一个节点的索引。
start指示第一个节点的索引。nextEmpty指示下一个节点将要插入的位置（下一个空位）。
诸如add、remove、get、size和insert之类的方法将使用start和nextEmpty，并可能对它们进行设置。例如，如果你remove了第一个项，start将被设置为下一个项的索引，而nextEmpty将被设置为被移除项的索引。
这个数组也可以在需要时进行扩展，就像ArrayList扩展其内部数组一样。
英文:
No, not at all. Here is just one of the many ways you can implement a linked list non-recurisvely (implementations of methods not shown):
class LinkedList {
private ListNode[] nodes;
private int start;
private int nextEmpty;
private static class ListNode {
private int val;
private int next;
}
}
Use an array to store the nodes. Each node has a value and a next. The next field stores the index of the next node in the array.
start indicates the index of the first node. nextEmpty indicates where the next node will be inserted (the next empty spot).
The methods like add, remove, get size and insert will make use of start and nextEmpty, and potentially set them. If you remove the first item for example, start will be set to the index of the next item, and nextEmpty will be set to the index of the removed item.
The array can also grow when needed, just like how ArrayList grows its internal array.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论