第4关：单链表的实现之查询功能 任务描述相关知识编程要求测试说明任务描述在上一关，我们实现了单链表的基本功能：添加元素，删除元素。链式实现的表无法实现随 |
您所在的位置：网站首页 › 在单链表中要取得某个元素 › 第4关：单链表的实现之查询功能 任务描述相关知识编程要求测试说明任务描述在上一关，我们实现了单链表的基本功能：添加元素，删除元素。链式实现的表无法实现随 |
|
第4关：单链表的实现之查询功能
注：第三关 复制第四关未更改代码（在93行加入返回值：return index;） 500 任务要求参考答案评论62 任务描述相关知识编程要求测试说明任务描述 在上一关，我们实现了单链表的基本功能：添加元素，删除元素。链式实现的表无法实现随机存取，因此要获取指定位置的元素，只能从头结点开始遍历。 本关任务：在上一关的基础上继续完善单链表的功能，实现获取指定位置元素的功能。 相关知识 请参考上一关 编程要求 本关的编程任务是补全右侧代码片段中Begin至End中间的代码，具体要求如下： 获取指定位置index处的元素并返回，补全get(int index)方法。 package step4; /** * Created by zengpeng on 2017/12/25. */ public class MyLinkedList { private Node first;//头结点，不存数据 private Node last;//指向链表的最后一个节点 private int size; public MyLinkedList() { size = 0; first = new Node(0, null); last = null; } /** * 添加到链表尾部 * * @param item */ public void add(int item) { final Node l = last; final Node node = new Node(item, null); last = node; if (first.next == null) {//首次添加 first.next = node; } else { l.next = node; } ++size; } /** * 添加数据item到指定位置index * index从0开始 * @param index * @param item */ public void add(int index, int item) { checkPosIndex(index); int n = index; Node l = first; while ((n--) > 0) { l = l.next; } final Node node = new Node(item, null); if (null == first.next) {//首次添加 last = node; } node.next = l.next; l.next = node; ++size; } /** * 删除指定位置index处的元素并返回, index从0开始 * @param index * @return */ public int remove(int index) { checkPosIndex(index); Node f = first; while ((index--) > 0) { f = f.next; } Node del = f.next; if (del == last) {//删除最后一个元素 last = f; } f.next = del.next; del.next = null; int oldVal = del.item; del = null; --size; return oldVal; } /** * 获取链表中第index个元素 * @param index * @return */ public int get(int index) { checkPosIndex(index); /********** Begin *********/ Node f = first.next; while ((index--) > 0) { f = f.next; } int out = f.item; return out; /********** End *********/ } public int size() { return size; } private void checkPosIndex(int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } //结点内部类 private static class Node { int item; Node next; Node(int item, Node next) { this.item = item; this.next = next; } } }------------------------------------------------------------------YU星河 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |