# 单链表必须递归定义吗？

go评论53阅读模式

Does singly linked list have to be defined recursively?

# 问题

``````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

``````class LinkedList {
private ListNode[] nodes;
private int start;
private int nextEmpty;

private static class ListNode {
private int val;
private int next;
}
}
``````

`start`指示第一个节点的索引。`nextEmpty`指示下一个节点将要插入的位置（下一个空位）。

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.

• 本文由 发表于 2020年10月6日 09:23:14
• 转载请务必保留本文链接：https://go.coder-hub.com/64218123.html
• java

go 102

go 64

go 61

go 97