Java实现单链表的操作
程序员文章站
2022-06-16 13:05:44
本文实例为大家分享了java实现单链表的基本操作,供大家参考,具体内容如下顺序表:物理上逻辑上都连续;链表:物理上不一定连续,逻辑上一定连续的。链表的概念及结构概念:连表示一种物理存储结构上非连续、非...
本文实例为大家分享了java实现单链表的基本操作,供大家参考,具体内容如下
顺序表:物理上逻辑上都连续;
链表:物理上不一定连续,逻辑上一定连续的。
链表的概念及结构
概念:连表示一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是用过链表中的引用链接次序实现的。
8种链表结构:
单项、双向
带头、不带头
循环、非循环
主要的三种链表:
无头单项非循环链表、带头循环单链表、不带头双向循环链表
代码实现
1. 接口定义
package com.github.linked.impl; public interface ilinked { // 头插法 void addfirst(int data); // 尾插法 void addlast(int data); // 任意位置插入,第一数据节点为0号下标 boolean addindex(int index, int data); // 查找是否包含关键字 key 在单链表中 boolean contains(int key); // 删除第一次出现的关键字为 key 的节点 int remove(int key); // 删除所有值为 key 的节点 void removeallkey(int key); // 得到单链表的长度 int getlength(); // 打印单链表 void display(); // 清空单链表以防内存泄漏 void clear(); }
2. 代码实现接口
package com.github.linked.impl; public class singlelisted implements ilinked { // 节点类 class node { private int data; private node next; public node(int data) { this.data = data; this.next = next; } } private node head; //头节点 public singlelisted() { this.head = head; } /** * 头插法 * @param data 要插入的数据 */ @override public void addfirst(int data) { // 1. 拿到一个实体 node node = new node(data); // 2. 插入 // 如果是第一次插入,直接到头节点 if (this.head == null) { this.head = node; } else { //不是第一次插入 node.next = this.head; // 插入的节点指向头节点 this.head = node; // 更新头节点 } } /** * 尾插法 * @param data 要插入的数据 */ @override public void addlast(int data) { // 1. 拿到一个实体 node node = new node(data); node cur = this.head; // 2. 插入 // 如果是第一次插入,直接到头节点 if (this.head == null) { this.head = node; } else { // 找尾巴 while (cur.next != null) { cur = cur.next; } // 退出上面的循环,cur所执行的位置就是尾节点 cur.next = node; } } // 检测 index 该下标是否合法 private void checkindex(int index) { if (index < 0 || index > getlength()) throw new indexoutofboundsexception("下标不合法!"); } // 找到下标为 index-1 位置的节点 private node searchindex(int index) { checkindex(index); if (index == 0) return null; int count = 0; // 记录行走的步数 node cur = this.head; while (cur.next != null && count < index-1) { cur = cur.next; count++; } return cur; } /** * 任意位置插入,第一数据节点为 0号下标 * @param index 插入的下标 * @param data 要插入的数据 * @return true */ @override public boolean addindex(int index, int data) { node node = new node(data); node cur = searchindex(index); // 如果链表为空,直接插入到头节点 if (cur == null) { node.next = this.head; this.head = node; } else { // 链表不为空,插入到 cur 的位置处 node.next = cur.next; // 将node链接到cur的下一个节点 cur.next = node; // 再将cur链接到node } return true; } /** * 查找是否包含关键字 key 在单链表中 * @param key 要查找的关键字 * @return 找到key返回true,否则返回false */ @override public boolean contains(int key) { node cur = this.head; while (cur != null) { if (cur.data == key) { return true; } cur = cur.next; } return false; } // 找第一次出现的关键字为 key 的节点的前驱 private node searchpre(int key) { // 1. 是不是第一个节点 if(head,data == key) node pre = this.head; if (pre.data == key) { // 或者 return null; return this.head; } // 2. if(cur.next.data == key) while (pre.next != null) { if (pre.next.data == key) { return pre; } pre = pre.next; } return null; } /** * 删除第一次出现的关键字为 key 的节点 * @param key 要删除的关键字 * @return olddata */ @override public int remove(int key) { int olddata = 0; node pre = searchpre(key); // 1. 若没有找到 if (pre == null) { // return -1; throw new unsupportedoperationexception("没有key的前驱"); } // 2. 找到了,并且在第一个节点 if (pre == this.head && pre.data == key){ olddata = this.head.data; this.head = this.head.next; return olddata; } // 3. 找到了,并且不在第一个节点 node delnode = pre.next; // 确定要删除的节点的位置 pre.next = delnode.next; // 让要删除的节点的前驱指向要删除的节点的后一个节点,进而删除该节点 return 0; } /** * 删除所有值为 key 的节点 * @param key 要删除的节点的值 */ @override public void removeallkey(int key) { node pre = this.head; node cur = this.head.next; // 遍历一遍链表 while (cur != null) { // 若找到了关键字,进行删除 if (cur.data == key) { pre.next = cur.next; cur = cur.next; } else { // 若不是关键字,继续查看链表的下一个 pre = cur; cur = cur.next; } if (this.head.data == key) { this.head = this.head.next; } } } /** * 得到单链表的长度 * @return 单链表长度 */ @override public int getlength() { node cur = this.head; int count = 0; // 节点的个数 while (cur != null) { count++; cur = cur.next; } return count; } /** * 打印单链表 */ @override public void display() { node cur = this.head; while (cur != null) { system.out.print(cur.data + " "); cur = cur.next; } system.out.println(); } /** * 清空单链表以防内存泄漏 */ @override public void clear() { while (this.head != null) { node cur = this.head.next; this.head.next = null; this.head = cur; } } }
3. 测试代码
package com.github.linked.impl; public class testdemo { public static void main(string[] args) { //mysinglelistimpl mysinglelist = new mysinglelistimpl(); singlelisted mysinglelist = new singlelisted(); mysinglelist.addfirst(10); mysinglelist.addfirst(20); mysinglelist.addfirst(30); mysinglelist.addfirst(40); mysinglelist.addfirst(50); system.out.println("头插:"); mysinglelist.display(); mysinglelist.addlast(100); mysinglelist.addlast(200); system.out.println("尾插:"); mysinglelist.display(); system.out.println(); system.out.print("单链表的长度:"); system.out.println(mysinglelist.getlength()); system.out.println(); mysinglelist.addindex(1,15); system.out.println("任意位置插入:"); mysinglelist.display(); system.out.println(); system.out.println("查找是否包含关键字 key 在单链表中:"); system.out.println("查找关键字125:"+mysinglelist.contains(125)); system.out.println("查找关键字30:"+mysinglelist.contains(30)); system.out.println(); system.out.println("删除第一次出现的关键字为 key 的节点:"); system.out.println("删除头节点50:"); mysinglelist.remove(50); //删除头节点 mysinglelist.display(); system.out.println("删除中间节点30:"); mysinglelist.remove(30); // 删除中间节点 mysinglelist.display(); system.out.println("删除尾节点200:"); mysinglelist.remove(200); // 删除尾节点 mysinglelist.display(); system.out.println(); system.out.println("删除第一次出现的关键字为 key 的节点:"); mysinglelist.addfirst(20); mysinglelist.display(); mysinglelist.removeallkey(20); mysinglelist.display(); system.out.println(); system.out.print("单链表的长度:"); system.out.println(mysinglelist.getlength()); system.out.println(); // 测试内存泄漏 try { thread.sleep(1000); system.out.println("睡醒了"); } catch (interruptedexception e) { e.printstacktrace(); } } }
4. 测试结果
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。