排序的链表维护顺序中插入元素
回答:
add()
下面的方法在列表中查找,直到找到合适的位置。然后,拼接中的新节点和更新start
,prev
以及curr
指针适用。
请注意,反向操作(即删除元素)不需要更改,因为您只是扔掉了东西,不会改变列表中的任何顺序。
实现方式:
爪哇
public void add(T x) {
Node newNode = new Node();
newNode.info = x;
// case: start is null; just assign start to the new node and return
if (start == null) {
start = newNode;
curr = start;
// prev is null, hence not formally assigned here
return;
}
// case: new node to be inserted comes before the current start;
// in this case, point the new node to start, update pointers, and return
if (x.compareTo(start.info) < 0) {
newNode.link = start;
start = newNode;
curr = start;
// again we leave prev undefined, as it is null
return;
}
// otherwise walk down the list until reaching either the end of the list
// or the first position whose element is greater than the node to be
// inserted; then insert the node and update the pointers
prev = start;
curr = start;
while (curr != null && x.compareTo(curr.info) >= 0) {
prev = curr;
curr = curr.link;
}
// splice in the new node and update the curr pointer (prev already correct)
newNode.link = prev.link;
prev.link = newNode;
curr = newNode;
}
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 排序的链表维护顺序中插入元素
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 排序的链表维护顺序中插入元素
常见问题FAQ
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。