Java单链表操作
Sasura_321 人气:0顺序表:物理上逻辑上都连续;
链表:物理上不一定连续,逻辑上一定连续的。
链表的概念及结构
概念:连表示一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是用过链表中的引用链接次序实现的。
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. 测试结果
加载全部内容