一、单链表介绍
- 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以节点来表示的,每个节点的构成:data域(数据元素)+next域(下一个结点的存储位置)。
- 单链表与数组相比的最大差别是:单链表的数据元素存放在内存空间的地址是不连续的,而数组的数据元素存放的地址在内存空间中是连续的,这也是为什么根据索引无法像数组那样直接就能查询到数据元素。
- 对于单链表的这种特殊结构,我们可以用“火车”来类比,假设一节车厢可以存储一个数据元素,当数据不够时,就新增一节车厢挂载在火车尾。在遍历时,只能从头部车厢开始遍历,依次走到尾部(即单向遍历,默认从前向后)。
代码实现:
public class SinglelinkedList { // 当前火车中车厢的节点个数(实际就是具体元素的个数) private int size; // 当前火车的火车头 private Node head; } class Node { // 存储具体数据 int val; // 保存下一个车厢的地址 Node next; public Node(int val) { this.val = val; } }二、链表的插入 *** 作 1.头插法
插入一个节点,首先要创建一节车厢。
Node node = new Node(val);
若火车为空,则当前节点就是头节点,否则-->
if(head == null){ head = node; }else{ node.next = head; head = next; }
代码实现:
public void addFirst(int val) { // 新建一个车厢节点 Node node = new Node(val); // 判断当前的火车是否为空 if (head == null) { head = node; }else { // 火车中有节点,要把当前新车厢挂载到火车头部 node.next = head; head = node; } size ++; }2.遍历一个单链表
只能从头结点开始依次向后遍历到车厢尾部。
public String toString() { String ret = ""; // 遍历火车这个类, // 从火车头(head)走到火车尾部 // 暂时存储当前头节点地址 Node node = head; while (node != null) { ret += node.val; ret += "->"; // 继续访问下一节车厢 node = node.next; } ret += "NULL"; return ret; }3.在链表中间位置插入
最核心的需要找到待插入位置的前驱节点!!(用prev表示)
addIndex(int index, int val);//在链表中间位置插入
- 首先判断index合法性
index < 0 || index > size //非法
- index = 0;//头插
- index在中间位置,例如 addIndex (1,7),首先创建一个节点node,如下图所示:
Node node = new Node(7);
代码实现:
public void addIndex(int index,int val){ //(1)判断合法性 if (index < 0 ||index > size){ System.err.println("add index illegal !"); return; } //2.插入元素 Node node = new Node(val); //需要找到待插入位置的前驱,从头节点开始向后依次走index-1步 Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } //此时prev指向待插入位置的前驱节点 node.next = prev.next; prev.next = node; size ++; }4.在链表尾部插入
可以直接调用addIndex()方法,但需要注意当index为0时,会抛出空指针异常,所以必须在addIndex()方法中添加index为0时的情况,代码实现如下:
public void addIndex(int index,int val){ //(1)判断合法性 if (index < 0 ||index > size){ System.err.println("add index illegal !"); return; } //头插法 if (index == 0){ addFirst(val); return; } //2.插入元素 Node node = new Node(val); //需要找到待插入位置的前驱,从头节点开始向后依次走index-1步 Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } //此时prev指向待插入位置的前驱节点 node.next = prev.next; prev.next = node; size ++; } //在单链表的尾部插入元素 public void addlast(int val){ addIndex(size,val); }三、链表的查询
1.查询index位置的元素值
get(int index);//返回index位置的元素值
代码实现:
public int get(int index){ if (rangecheck(index)){ //index 合法 //从头节点开始遍历链表,走到index位置 Node node = head; //规定了node节点走的步数 for (int i = 0; i < index; i++) { node = node.next; } return node.val; }else{ System.err.println("get index illegal"); return -1; } }
node节点的遍历过程:
2.查询值为value的元素是否在单链表中存在
contains(int value);
代码实现:
public boolean contains(int val){ for(Node temp = head;temp != null;temp = temp.next){ if (temp.val == val){ return true; } } return false; }
3.索引的区间检查
判断合法性 :index < 0 || index >= size 不合法
所有访问类型(删改查)的index均不能取到size,所以可以将合法性判断抽象为一个方法,
//判断用户输入的index是否合法,只在类内部使用 private boolean rangecheck(int index){ if (index < 0 || index >= size){ return false; } return true; }四、单链表的修改
1.将index位置的值修改为value
set(int index,int newvalue);
代码实现:
public int set(int index, int newVal){ if (rangecheck(index)){ Node node = head; for (int i = 0; i五、单链表的删除 1.删除单链表中index节点 removeIndex(int index);//删除单链表中index节点
- index=0,删除头节点。在单链表的插入与删除 *** 作中,都需要找到前驱节点才能进行下一步 *** 作,只有头节点没有前驱节点,所以需要单独处理。
- 注意:当一个节点没有任何引用指向时,就可以被释放空间,所以需要将head.next = null;
- 引入一个临时变量存储原先head节点的地址:
Node temp = head; temp.next = null;//将头节点真正从链表中断开
- index != 0 时
代码实现:
public void removeIndex(int index){ //1.判断合法性 if (rangecheck(index)){ //2.边界 删除头节点的情况 if (index == 0){ Node temp = head; head = head.next; temp.next = null; }else{ //index是中间位置 //找到待删除节点的前驱 Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } //cur是待删除节点 Node cur = prev.next; prev.next = cur.next; cur.next = null; size --; } }else{ System.err.println("remove index illegal !"); } } public void removeFirst(){ removeIndex(0); } public void removeLast(){ //尾部节点索引值为size-1 removeIndex(size-1); }2.按值删除(1)删除单链表中第一个值为value的节点
removevalueonce(int value);//删除单链表中第一个值为value的节点
- 依然可以分为两种情况,当 head.val = val 时,直接删除头节点。
- 当head不是待删除节点时:
Node prev = head; //prev指向待删除的前驱,要判断前驱的下一个节点值是否等于val while(prev.next != null){ //cur 就是待删除的节点 if (prev.next.val == val){ Node cur = prev.next; cur.next = null; size --; return; } //如果不走if分支,说明prev不是待删除节点的前驱,让prev向后移动 prev = prev.next; }代码实现:
public void removevalueonce(int val){ //遍历链表,找到值为val的节点->不知道值为val的节点在哪个位置 //找到后删除(正常的删除都需要找到前驱,只有头节点没有前驱) if (head != null && head.val == val){ //头节点就是待删除节点 Node temp = head; head = head.next; temp.next = null; size --; }else{ //此时head一定不是待删除节点 Node prev = head; //prev指向待删除的前驱,要判断前驱的下一个节点值是否等于val while(prev.next != null){ //cur 就是待删除的节点 if (prev.next.val == val){ Node cur = prev.next; cur.next = null; size --; return; } //如果不走if分支,说明prev不是待删除节点的前驱,让prev向后移动 prev = prev.next; } } }(2) 删除单链表中所有值为value的节点
removevalueAll(int value);//删除单链表中所有值为value的节点
- 注意事项:
a.只有当确保prev.next不是待删除的节点时才能移动prev指向.
b.保证prev一定不是待删除节点,如果prev是待删除节点,那该节点一定删不掉.
- 代码实现:
public void removevalueAll(int val){ //判断头节点是否为待删除节点 while(head != null && head.val == val){ head = head.next; size --; } if (head == null){ //此时链表中全是val且已经被删空 return; }else{ //此时head一定不是待删除节点,且链表中还有节点 Node prev = head ; while(prev.next != null){ if(prev.next.val ==val){ //此时prev.next就是待删除节点 Node cur = prev.next; prev.next = cur.next; cur.next = null; size --; }else{ //只有当确保prev.next不是待删除的节点时才能移动prev指向 //保证prev一定不是待删除节点,如果prev是待删除节点,那该节点一定删不掉 prev = prev.next; } } } }总结:链表中的查和改都需要遍历,时间复杂度都是O(N);而数组时间复杂度均是O(1);
所以如果需要频繁的查和改,可以使用数组;如果频繁地添加和删除,就可以使用链表。
六、虚拟头结点
- 通过对以上内容的学习,我们发现在单链表的中间位置插入和删除元素时,都需要找到待处理位置的前驱节点prev,但因为头节点是没有前驱的,所以需要把头节点特殊处理。
- 思考一下如何能将所有节点“一视同仁”,使它们都有前驱,这样的话就可以不用单独处理头节点。基于此我们可以引出一个虚拟头节点,这个节点不存储具体的值,只是作为链表的头部。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)