Java实现单链表的操作

Java实现单链表的操作

本文实例为大家分享了java实现单链表的基本操作，供大家参考，具体内容如下

顺序表：物理上逻辑上都连续；链表：物理上不一定连续，逻辑上一定连续的。

链表的概念及结构

概念：连表示一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是用过链表中http://的引用链接次序实现的。

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 要删除的节点的值

*/

http://@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："+mySingleLishttp://t.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. 测试结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。