【数据结构和算法】第七锻造，链表真身

转x33g5p2x  于2021-12-07 转载在 其他  
字(5.5k)|赞(0)|评价(0)|浏览(422)

一、前言

二、链表的简介

三、单向链表的API设置

代码实现

结点类：链表的设置结点类少不了

成员变量和构造方法

清空链表，链表的长度，链表是否为空

获取指定位置处的元素

插入元素t(在链表的最后以结点后插入元素)

在指定i处，添加元素t

删除指定位置i处的元素并返回被删除的元素

查找元素t在链表中第一次出现的位置

提供一个遍历的方法，实现Iterable接口

全部代码概览：

测试类下：

运行效果图： 

四、鲁迅说：一个是关于head.next，另一个也是head.next

一、前言

链表是一个和数组不一样的存储方式。我们都知道数组的存储地址是连续的，这样就不能很好的利

用好内存空间，而链表就解决了这个问题，链表是一存储地址不连续的的存储结构，这样的好处

就是能节省空间。

二、链表的简介

链表是由一系列的结点构成的，链表的第一个元素为头结点，头结点的特点是；不存放具体的数

表示单链表的表头，比如要找一个结点就是从头结点一个一个往下找的。 

每一个结点有一个类似于指针的next，用来指向下一个结点，和一个date区域用于存储数据

头结点不存放数据，最后一个结点不指向null。

三、单向链表的API设置

 代码实现

  1. //定义节点类(成员内部类)
  2.     private class Node{
  3.         //存储数据
  4.         T item;
  5.         //下一个节点
  6.         Node next;
  7.         public Node(T item,Node next){
  8.             this.item=item;
  9.             this.next=next;
  10.         }
  11.     }
  1. //记录头节点
  2.     private Node head;
  3.     //记录链表的长度
  4.     private int N;
  5.     //构造方法用来初始化成员变量
  6.     public LinkList(){
  7.         this.head=new Node(null,null);
  8.         this.N=0;
  9.     }
  1. //方法1：清空链表
  2.     public void clear(){
  3.         head.next=null;//将头结点的指向置空
  4.         this.N=0;//元素个数变为0
  5.     }
  6.     //方法2：链表的长度
  7.     public int length(){
  8.         return N;//N就是链表长度
  9.     }
  10.     //方法3：判断链表是否为空
  11.     public boolean isEmpty(){
  12.         return this.N==0;//只需判断N是否为0即可
  13.     }
  1. //方法4：获取指定位置处的元素
  2.     public T get(int i){
  3.              Node node=head.next;//node是下一个结点
  4.           if(node!=null){//有下一个结点
  5.             for(int index=0;index<i;index++){
  6.                 node=node.next;//往下一个结点移动
  7.             }
  8.             return node.item;
  9.         }
  10.         return null;
  11.     }
  1. //方法5：插入元素t(在链表的最后以结点后插入元素)
  2.     public void insert(T t){
  3.         //创建一个结点
  4.         Node node=head;
  5.         while(node.next!=null){//找到最后一个结点的前一个结点
  6.             node=node.next;
  7.         }
  9.         Node newLast=new Node(t, null);
  10.         //之前的最后指向现在的最后结点
  11.        node.next=newLast;
  12.        //元素个数加一
  13.         N++;
  14.     }
  1. //方法6：在指定i处，添加元素t
  2.     public void insert(int i,T t){
  3.         //创建一个结点，从头结点开始
  4.         Node node =head;
  5.         for(int index=0;index<i;index++){//找到i位置处的前一个元素
  6.             node=node.next;
  7.         }
  8.         //当前i位置的结点
  9.         Node oldNode=node.next;
  10.         //创建结点t
  11.         Node newNode=new Node(t, null);
  12.         //此时node表示的还是前一个结点，所以只需要把前一个结点指向创建的新结点
  13.         node.next=newNode;
  14.         //新结点指向原来i位置处的结点，即可完成连接
  15.         newNode.next=oldNode;
  16.         //元素个数加一
  17.         N++;
  18.     }
  1. //方法7：删除指定位置i处的元素并返回被删除的元素
  2.     public T remove(int i) {
  3.         //创建一个结点，从头节点开始
  4.         Node node=head;
  5.         //因为是从头结点开始的，所以下面循环会找到i位置的前一个结点
  6.         for(int index=0;index<i;index++){
  7.             node=node.next;
  8.         }
  9.         //i位置处的结点
  10.         Node iNode=node.next;
  11.         //直接让i位置处的前以结点指向i位置的后一结点就可以删除i位置处的结点
  12.         node.next=iNode.next;//或者也可以node.next=node.next.next;
  13.         //元素减1
  14.         N--;
  15.         return iNode.item;
  16.     }
  1. //方法8：查找元素t在链表中第一次出现的位置
  2.     public int indexOf(T t){
  3.         Node node=head;
  4.         for(int index=0;node.next!=null;index++){
  5.             node=node.next;
  6.             if(node.item.equals(t)){
  7.                 return index;
  8.             }
  10.         }
  11.         //找不到
  12.         return -1;
  13.     }
  1. public class LinkList<T> implements Iterable{}
  1. //实现Iterable接口，重写iterator方法
  2.     @Override
  3.     //因为要的接口对象(接口不能直接new)，所以我们必须创建一个对象去实现这个接口
  4.     public Iterator iterator() {
  5.         return new LIterator()  ;
  6.     }
  7.     public class LIterator implements Iterator{
  8.      //实现Iterator接口重写hasNext()和next()两个方法
  9.         private Node n;
  10.         public LIterator(){
  11.             this.n=head;//从头结点开始
  12.         }
  13.         @Override
  14.         public boolean hasNext() {//是否有元素
  15.             return n.next!=null;
  16.         }
  18.         @Override
  19.         public Object next() {//返回下一个元素
  20.             n=n.next;
  21.             return n.item;
  22.         }
  23.     }

全部代码概览：

  1. import java.util.Iterator;
  3. public class LinkList<T> implements Iterable{
  5.     //定义节点类
  6.     private class Node{
  7.         //存储数据
  8.         T item;
  9.         //下一个节点
  10.         Node next;
  11.         public Node(T item,Node next){
  12.             this.item=item;
  13.             this.next=next;
  14.         }
  15.     }
  16.     //记录头节点
  17.     private Node head;
  18.     //记录链表的长度
  19.     private int N;
  20.     //构造方法用来初始化成员变量
  21.     public LinkList(){
  22.         this.head=new Node(null,null);
  23.         this.N=0;
  24.     }
  25.     //方法1：清空链表
  26.     public void clear(){
  27.         head.next=null;//将头结点的指向置空
  28.         this.N=0;//元素个数变为0
  29.     }
  30.     //方法2：链表的长度
  31.     public int length(){
  32.         return N;//N就是链表长度
  33.     }
  34.     //方法3：判断链表是否为空
  35.     public boolean isEmpty(){
  36.         return this.N==0;//只需判断N是否为0即可
  37.     }
  38.     //方法4：获取指定位置处的元素
  39.     public T get(int i){
  40.              Node node=head.next;//node是下一个结点
  41.           if(node!=null){//有下一个结点
  42.             for(int index=0;index<i;index++){
  43.                 node=node.next;//往下一个结点移动
  44.             }
  45.             return node.item;
  46.         }
  47.         return null;
  48.     }
  49.     //方法5：插入元素t(在链表的最后以结点后插入元素)
  50.     public void insert(T t){
  51.         //创建一个结点
  52.         Node node=head;
  53.         while(node.next!=null){//找到最后一个结点的前一个结点
  54.             node=node.next;
  55.         }
  57.         Node newLast=new Node(t, null);
  58.         //之前的最后指向现在的最后结点
  59.        node.next=newLast;
  60.        //元素个数加一
  61.         N++;
  62.     }
  63.     //方法6：在指定i处，添加元素t
  64.     public void insert(int i,T t){
  65.         //创建一个结点，从头结点开始
  66.         Node node =head;
  67.         for(int index=0;index<i;index++){//找到i位置处的前一个元素
  68.             node=node.next;
  69.         }
  70.         //当前i位置的结点
  71.         Node oldNode=node.next;
  72.         //创建结点t
  73.         Node newNode=new Node(t, null);
  74.         //此时node表示的还是前一个结点，所以只需要把前一个结点指向创建的新结点
  75.         node.next=newNode;
  76.         //新结点指向原来i位置处的结点，即可完成连接
  77.         newNode.next=oldNode;
  78.         //元素个数加一
  79.         N++;
  80.     }
  81.     //方法7：删除指定位置i处的元素并返回被删除的元素
  82.     public T remove(int i) {
  83.         //创建一个结点，从头节点开始
  84.         Node node=head;
  85.         //因为是从头结点开始的，所以下面循环会找到i位置的前一个结点
  86.         for(int index=0;index<i;index++){
  87.             node=node.next;
  88.         }
  89.         //i位置处的结点
  90.         Node iNode=node.next;
  91.         //直接让i位置处的前以结点指向i位置的后一结点就可以删除i位置处的结点
  92.         node.next=iNode.next;//或者也可以node.next=node.next.next;
  93.         //元素减1
  94.         N--;
  95.         return iNode.item;
  96.     }
  97.     //方法8：查找元素t在链表中第一次出现的位置
  98.     public int indexOf(T t){
  99.         Node node=head;
  100.         for(int index=0;node.next!=null;index++){
  101.             node=node.next;
  102.             if(node.item.equals(t)){
  103.                 return index;
  104.             }
  106.         }
  107.         //找不到
  108.         return -1;
  109.     }
  110.     //实现Iterable接口，重写iterator方法
  111.     @Override
  112.     //因为要的接口对象(接口不能直接new)，所以我们必须创建一个对象去实现这个接口
  113.     public Iterator iterator() {
  114.         return new LIterator()  ;
  115.     }
  116.     public class LIterator implements Iterator{
  117.      //实现Iterator接口重写hasNext()和next()两个方法
  118.         private Node n;
  119.         public LIterator(){
  120.             this.n=head;//从头结点开始
  121.         }
  122.         @Override
  123.         public boolean hasNext() {//是否有元素
  124.             return n.next!=null;
  125.         }
  127.         @Override
  128.         public Object next() {//返回下一个元素
  129.             n=n.next;
  130.             return n.item;
  131.         }
  132.     }
  133. }

测试类下：

  1. public class LinkListText {
  2.     public static void main(String[] args) {
  3.         //创建链表对象
  4.         LinkList<String> list=new LinkList<String>();
  5.         list.insert("张三");
  6.         list.insert("李四");
  7.         list.insert("王五");
  8.         list.insert("李四");
  9.         System.out.println("链表为空吗："+list.isEmpty());
  10.         for(Object s:list){
  11.             System.out.println(s);
  12.         }
  13.         //元素个数
  14.         System.out.println("初始元素个数："+list.length());
  15.         System.out.println("----------------------");
  16.         //插入
  17.         list.insert(1,"赵六");
  18.         list.insert(2,"历七");
  19.         //元素个数
  20.         System.out.println("插入后元素个数:"+list.length());
  21.        //第一次出现的位置
  22.         System.out.println("张三第一次出现的位置:"+list.indexOf("张三"));
  23.         System.out.println("----------------------");
  24.         for(Object s:list){
  25.         System.out.println(s);
  26.     }
  27.         //清除链表
  28.         list.clear();
  29.         System.out.println("清除后，链表为空吗："+list.isEmpty());
  31.     }
  32. }

运行效果图： 

四、鲁迅说：一个是关于head.next，另一个也是head.next

有关于左右边的.next解读：

** 左边的.next表示的是指向，右边的.next表示的下一个元素。**

一般来说在左边的是指向，在右边的是下一个元素。（这里.next前可以是任意非null结点）

head.next!=null一样的道理。

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_60719453/article/details/121706004

内容来源于网络，如有侵权，请联系作者删除！

数据结构算法链表数据结构和算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com