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

大家好，欢迎来到IT知识分享网。

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

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); } } }