• 【数据结构链表（一）】一一一一单向链表
• • 1、:apple: 什么是单向链表
  • 2、:banana: 概念
  • 3、:orange: 链表特点
  • 4、:jack_o_lantern: 单向链表的实现原理
  • • 4.1 :first_quarter_moon_with_face: 单向链表的实现类
    • 4.2 :b: 如何自己实现链表
    • • 4.2.1 :one: 创建一个节点类
      • 4.2.2 :two: 创建链表类

【数据结构链表（一）】一一一一单向链表

1、🍎 什么是单向链表

​ 链表包含单链表，双向链表，循环链表等等。相对于线性表，添加，删除操作非常方便，因为不用移动大量的节点，只需要修改对应的前后节点指针即可。下面用一个具体实例来说明下这种结构。现在有一需求，是将具有不同编号，姓名，昵称的人添加到系统中。首先需要创建节点，既然是链表，节点除了基本信息也要加入下一节点指针，方便计算机在内存中查找。

​ 单向链表是通过指针构建的列表，基本结构就是头节点+下一节点地址指针—>节点+下一节点地址指针—>尾节点。

2、🍌 概念

**单链表：**用一个指向后继元素的指针将具有线性关系的各个结点链接起来，并且最后一个节点的后继指针为空指针。

3、🍊 链表特点

1. 获取数据麻烦，需要遍历查找，比数组慢
2. 方便插入、删除

4、🎃 单向链表的实现原理

1. 创建一个节点类，其中节点类包含两个部分，第一个是数据域（你到时候要往节点里面储存的信息），第二个是引用域（相当于指针，单向链表有一个指针，指向下一个节点；双向链表有两个指针，分别指向下一个和上一个节点）
2. 创建一个链表类，其中链表类包含三个属性：头结点、尾节点和大小，方法包含添加、删除、插入等等方法。

4.1 🌛 单向链表的实现类

public class Node {public Object data;public Node next;public Node(Object e){this.data = e;}
}

4.2 🅱️ 如何自己实现链表

4.2.1 1️⃣ 创建一个节点类

💅:注意这里的类节点是创建链表类的一个内部类；

/*** @author xiaoCoder* @version 1.0* @description: TODO 单向列表实现* @date 2021/7/29 15:03*/private class Node {private T data;// 数据信息private Node next;// 下一节点的引用public Node() {}public Node(T data) {this.data = data;}// 添加节点public void add(T data) {if (this.next == null) {this.next = new Node(data); // 如果当前节点为空就直接添加} else {this.next.add(data);}}public T get(int index) {if (ListDemoXiao.this.foot++ == index) {return this.data;} else {return this.next.get(index);}}public boolean contains(T data) {if (this.data.equals(data)) {return true;} else {if (this.next == null) {return false;} else {return this.next.contains(data);}}}public void replace(T oldData, T newData) {if (this.data.equals(oldData)) {this.data = newData;} else {if (this.next == null) {System.out.println("没有找到替换的元素！");} else {this.next.replace(oldData, newData);}}}public void remove(Node previous, T data) {if (this.data.equals(data)) {previous.next = this.next;this.next = null;ListDemoXiao.this.count--;return;} else {if (this.next != null) {this.next.remove(this, data);} else {return;}}}public void remove(Node previous, int index) {if (ListDemoXiao.this.foot++ == index) {previous.next = this.next;this.next = null;ListDemoXiao.this.count--;}else {this.next.remove(this,index);}}}

4.2.2 2️⃣ 创建链表类

package com.dataStructure;/*** @author xiaoCoder* @version 1.0* @description: TODO 单向列表实现* @date 2021/7/29 15:03*/
public class ListDemoXiao<T> {public static void main(String[] args) {ListDemoXiao<String> myList = new ListDemoXiao<>();myList.add("111");myList.add("222");myList.add("333");myList.add("444");myList.add("555");//System.out.println(myList.get(1));//System.out.println(myList.contains("222"));//myList.replace("222", "dasdsad");//System.out.println(myList.get(1));Object[] objects = myList.toArray();for (Object object : objects) {System.out.println(object.toString());}System.out.println("rrrrrrrrrrrrrrrrrrrrr");//myList.remove("111");//for (Object o : myList.toArray()) {//    System.out.println(o.toString());//}myList.remove(1);for (Object o : myList.toArray()) {System.out.println(o.toString());}}private int foot; // 根节点索引的位置private int count;// 链表的长度private Node root;// 标识根节点private class Node {private T data;// 数据信息private Node next;// 下一节点的引用public Node() {}public Node(T data) {this.data = data;}// 添加节点public void add(T data) {if (this.next == null) {this.next = new Node(data); // 如果当前节点为空就直接添加} else {this.next.add(data);}}// 根据索引获取数据public T get(int index) {if (ListDemoXiao.this.foot++ == index) {return this.data;} else {return this.next.get(index);}}// 查看链表中是否包含当前数据public boolean contains(T data) {if (this.data.equals(data)) {return true;} else {if (this.next == null) {return false;} else {return this.next.contains(data);}}}// 根据数据来替换对应的数据信息public void replace(T oldData, T newData) {if (this.data.equals(oldData)) {this.data = newData;} else {if (this.next == null) {System.out.println("没有找到替换的元素！");} else {this.next.replace(oldData, newData);}}}// 找到相同的node节点进行删除public void remove(Node previous, T data) {if (this.data.equals(data)) {previous.next = this.next;this.next = null;ListDemoXiao.this.count--;return;} else {if (this.next != null) {this.next.remove(this, data);} else {return;}}}// 根据索引值删除对呀的node节点public void remove(Node previous, int index) {if (ListDemoXiao.this.foot++ == index) {previous.next = this.next;this.next = null;ListDemoXiao.this.count--;}else {this.next.remove(this,index);}}}public boolean isEmpty() {return (count == 0 || this.root == null);}// 往链表中加入数据public void add(T data) {if (this.isEmpty()) {this.root = new Node(data);} else {this.root.add(data);}this.count++;}// 获取链表中指定索引上的数据public T get(int index) {if (this.isEmpty()) {return null;}this.foot = 0;return this.root.get(index);}public boolean contains(T data) {if (this.isEmpty()) {return false;}return this.root.contains(data);}public void replace(T oldData, T newData) {if (this.isEmpty()) {return;}this.root.replace(oldData, newData);}public Object[] toArray() {if (this.isEmpty()) return null;int count = this.count;Object[] objects = new Object[count];for (int i = 0; i < objects.length; i++) {objects[i] = this.get(i);}return objects;}/*** 根据传入的数值进行删除** @param data*/public void remove(T data) {if (this.isEmpty()) return;if (this.root.data.equals(data)) {// 删除的正好是根节点Node temp = this.root;this.root = this.root.next;temp.next = null;this.count--;return;} else {this.root.remove(this.root, data);}}/***  Delete based on the index* @param index*/public void remove(int index) {if (this.isEmpty()) {return;}if (index < 0 || this.count <= index) {return;}if (index == 0) {Node temp = this.root;this.root = this.root.next;temp.next = null;this.count--;return;} else {this.foot = 0;this.root.remove(this.root, index);}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！