单链表的讲解:单链表的原理,添加、删除元素 |
您所在的位置:网站首页 › 单向链表删除元素怎么删 › 单链表的讲解:单链表的原理,添加、删除元素 |
单链表及其节点 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域, 一个域用于数据元素的存储,另一个域是指向其他单元的指针。 这里具有一个数据域和多个指针域的存储单元通常称为 结点(node) 一种最简单的结点结构如图所示,它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素, 指针域用于指向下一个具有相同结构的结点。 因为只有一个指针结点,称为单链表 单链表的查询、添加、删除操作分析 查询操作 在单链表中进行查找操作,只能从链表的首结点开始,通过每个结点的 next 引用来一次访问链表中的每个结点以完成相应的查找操作。 例如需要在单链表中查找是否包含某个数据元素 e,则方法是使用一个循环变量 p,起始时从单链表的头结点开始, 每次循环判断 p所指结点的数据域是否和 e 相同,如果相同则可以返回 true,否则让p指向下一个节点,继续循环直到链表中所有 结点均被访问,此时 p 为 null 关键操作: 1.起始条件:p = head; 2.结束条件: 找到:e.equals(p.getData())==true 未找到 p == null 3.p指向下一个结点: p = p.getNext(); 缺点:逐个比较,频繁移动指针,导致效率低下 注意:如果要查询第i个元素的值,无法直接定位,也只能从首结点开始逐个移动到第i个结点,效率同样低下。 添加操作 在单链表中数据元素的插入,是通过在链表中插入数据元素所属的结点来完成的。 对于链表的不同位置,插入的过程会有细微的差别。 中间、末尾的添加过程其实是一样的,关键是在首部添加,会有不同,会改变整个单链表的起始结点。 以添加中间结点为例 1.指明新结点的后继 s.setNext(p.getNext()); 或者 s.next = p.next 2.指明新结点的前驱(其实是指明前驱结点的后继是新结点) p.setNext(s) 或者 p.next = s; 添加节点不需要移动元素,只需要修改元素的指针即可,效率高。 但是如果需要先查询到添加位置再添加新元素,因为有逐个查询的过程,效率不高。 删除操作 类似添加操作 单链表的代码实现: /** * 单链表 * @author Administrator * */ public class SingleLinkedList implements List{ public Node head = new Node();//只有一个头结点 public int size;//默认长度是0,头结点不算 public SingleLinkedList(){ } @Override public int size() { return size; } /** * 和数组可是不一样了!!! */ @Override public Object get(int i) { return null; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean contains(Object e) { return this.indexOf(e)>=0; } @Override public int indexOf(Object e) { Node p = head.getNext(); for(int i = 0 ;i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |