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. 测试结果
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
java实现单链表中是否有环的方法详解
这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在:如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈). 如果环不存在,一定是h2先碰到NULL: 如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇
-
java实现单链表之逆序
下面一段代码准确的介绍了java实现单链表逆序,具体内容就不做详解了,有需要的朋友可以直接拷贝了 package com.ckw.mianshi; /** * java 实现单链表的逆序 * @author Administrator * */ public class SingleLinkedReverse { class Node{ int data; Node next; public Node(int data){ this.data = data; } } public static
-
java 实现单链表逆转详解及实例代码
java 实现单链表逆转详解 实例代码: class Node { Node next; String name; public Node(String name) { this.name = name; } /** * 打印结点 */ public void show() { Node temp = this; do { System.out.print(temp + "->"); temp = temp.next; }while(temp != null); System.o
-
java实现单链表增删改查的实例代码详解
package 数据结构算法.链表; /* *定义节点 * 链表由节点构成 */ public class Node<E> { private E e; //数据data private Node<E> next; //指向下一个节点 public Node() { } public Node(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node&l
-
java实现数据结构单链表示例(java单链表)
复制代码 代码如下: /** * 单向链表 * */public class NodeList<E> { private static class Node<E> { // 节点类 E data; // 节点上的数据 Node<E> next; // 指向下一个节点 Node(E e) { this.data = e; this.next = null; } } private Node<E> head; // 链表的头节点 private N
-
Java模拟单链表和双端链表数据结构的实例讲解
模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1．集合中必存在唯一的一个"第一元素": 2．集合中必存在唯一的一个 "最后元素" : 3．除最后一个元素之外,均有 唯一的后继(后件):
-
Java实现单链表翻转实例代码
Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node
-
Java单链表基本操作的实现
最近被问到链表,是一个朋友和我讨论Java的时候说的.说实话,我学习编程的近一年时间里,学到的东西还是挺少的.语言是学了Java和C#,关于Web的学了一点Html+css+javascript.因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究.但链表这个东西我还真没有学习和研究过,加上最近自己在看WPF,而课程也到了JSP了,比较紧. 但是我还是抽了一个晚上加半天的时间看了一下单向链表.并且使用Java试着写了一个实例出来.没有接触过链表的朋友可以作为参考,希望大家多提宝贵
-
Java数据结构之简单链表的定义与实现方法示例
本文实例讲述了Java数据结构之简单链表的定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 只有一个数据项(链接点Link),每个数据插入时都是对第一个数据的引用. 2.插入数据说明: 当链表没有数据时,插入的值就是第一个数据,如果链表里有数据,就把当前的数据的next指针指向第一个数据. 3.插入数据图: 4.特点:先进后出 5.实现功能: 数据插入,指定位置插入,显示,查询,删除等 6.删除原理 7.插入头节点原理 二.实现: 1.创建节点 /** * @描述 节点
-
Java单链表的实现代码
下面是小编给大家分享的一个使用java写单链表,有问题欢迎给我留言哦. 首先定义一个Node类 public class Node { protected Node next; //指针域 public int data;//数据域 public Node( int data) { this. data = data; } //显示此节点 public void display() { System. out.print( data + " "); } } 接下来定义一个单链表,并实现