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

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

一、前言

二、链表的简介

三、单向链表的API设置

代码实现

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

成员变量和构造方法

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

获取指定位置处的元素

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

在指定i处，添加元素t

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

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

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

全部代码概览：

测试类下：

运行效果图： 

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

一、前言

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

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

就是能节省空间。

二、链表的简介

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

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

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

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

三、单向链表的API设置

 代码实现

//定义节点类(成员内部类)
    private class Node{
        //存储数据
        T item;
        //下一个节点
        Node next;
        public Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }
//记录头节点
    private Node head;
    //记录链表的长度
    private int N;
    //构造方法用来初始化成员变量
    public LinkList(){
        this.head=new Node(null,null);
        this.N=0;
    }
//方法1：清空链表
    public void clear(){
        head.next=null;//将头结点的指向置空
        this.N=0;//元素个数变为0
    }
    //方法2：链表的长度
    public int length(){
        return N;//N就是链表长度
    }
    //方法3：判断链表是否为空
    public boolean isEmpty(){
        return this.N==0;//只需判断N是否为0即可
    }
//方法4：获取指定位置处的元素
    public T get(int i){
             Node node=head.next;//node是下一个结点
          if(node!=null){//有下一个结点
            for(int index=0;index<i;index++){
                node=node.next;//往下一个结点移动
            }
            return node.item;
        }
        return null;
    }
//方法5：插入元素t(在链表的最后以结点后插入元素)
    public void insert(T t){
        //创建一个结点
        Node node=head;
        while(node.next!=null){//找到最后一个结点的前一个结点
            node=node.next;
        }

        Node newLast=new Node(t, null);
        //之前的最后指向现在的最后结点
       node.next=newLast;
       //元素个数加一
        N++;
    }
//方法6：在指定i处，添加元素t
    public void insert(int i,T t){
        //创建一个结点，从头结点开始
        Node node =head;
        for(int index=0;index<i;index++){//找到i位置处的前一个元素
            node=node.next;
        }
        //当前i位置的结点
        Node oldNode=node.next;
        //创建结点t
        Node newNode=new Node(t, null);
        //此时node表示的还是前一个结点，所以只需要把前一个结点指向创建的新结点
        node.next=newNode;
        //新结点指向原来i位置处的结点，即可完成连接
        newNode.next=oldNode;
        //元素个数加一
        N++;
    }
//方法7：删除指定位置i处的元素并返回被删除的元素
    public T remove(int i) {
        //创建一个结点，从头节点开始
        Node node=head;
        //因为是从头结点开始的，所以下面循环会找到i位置的前一个结点
        for(int index=0;index<i;index++){
            node=node.next;
        }
        //i位置处的结点
        Node iNode=node.next;
        //直接让i位置处的前以结点指向i位置的后一结点就可以删除i位置处的结点
        node.next=iNode.next;//或者也可以node.next=node.next.next;
        //元素减1
        N--;
        return iNode.item;
    }
//方法8：查找元素t在链表中第一次出现的位置
    public int indexOf(T t){
        Node node=head;
        for(int index=0;node.next!=null;index++){
            node=node.next;
            if(node.item.equals(t)){
                return index;
            }

        }
        //找不到
        return -1;
    }
public class LinkList<T> implements Iterable{}
//实现Iterable接口，重写iterator方法
    @Override
    //因为要的接口对象(接口不能直接new)，所以我们必须创建一个对象去实现这个接口
    public Iterator iterator() {
        return new LIterator()  ;
    }
    public class LIterator implements Iterator{
     //实现Iterator接口重写hasNext()和next()两个方法
        private Node n;
        public LIterator(){
            this.n=head;//从头结点开始
        }
        @Override
        public boolean hasNext() {//是否有元素
            return n.next!=null;
        }

        @Override
        public Object next() {//返回下一个元素
            n=n.next;
            return n.item;
        }
    }

全部代码概览：

import java.util.Iterator;

public class LinkList<T> implements Iterable{

    //定义节点类
    private class Node{
        //存储数据
        T item;
        //下一个节点
        Node next;
        public Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }
    //记录头节点
    private Node head;
    //记录链表的长度
    private int N;
    //构造方法用来初始化成员变量
    public LinkList(){
        this.head=new Node(null,null);
        this.N=0;
    }
    //方法1：清空链表
    public void clear(){
        head.next=null;//将头结点的指向置空
        this.N=0;//元素个数变为0
    }
    //方法2：链表的长度
    public int length(){
        return N;//N就是链表长度
    }
    //方法3：判断链表是否为空
    public boolean isEmpty(){
        return this.N==0;//只需判断N是否为0即可
    }
    //方法4：获取指定位置处的元素
    public T get(int i){
             Node node=head.next;//node是下一个结点
          if(node!=null){//有下一个结点
            for(int index=0;index<i;index++){
                node=node.next;//往下一个结点移动
            }
            return node.item;
        }
        return null;
    }
    //方法5：插入元素t(在链表的最后以结点后插入元素)
    public void insert(T t){
        //创建一个结点
        Node node=head;
        while(node.next!=null){//找到最后一个结点的前一个结点
            node=node.next;
        }

        Node newLast=new Node(t, null);
        //之前的最后指向现在的最后结点
       node.next=newLast;
       //元素个数加一
        N++;
    }
    //方法6：在指定i处，添加元素t
    public void insert(int i,T t){
        //创建一个结点，从头结点开始
        Node node =head;
        for(int index=0;index<i;index++){//找到i位置处的前一个元素
            node=node.next;
        }
        //当前i位置的结点
        Node oldNode=node.next;
        //创建结点t
        Node newNode=new Node(t, null);
        //此时node表示的还是前一个结点，所以只需要把前一个结点指向创建的新结点
        node.next=newNode;
        //新结点指向原来i位置处的结点，即可完成连接
        newNode.next=oldNode;
        //元素个数加一
        N++;
    }
    //方法7：删除指定位置i处的元素并返回被删除的元素
    public T remove(int i) {
        //创建一个结点，从头节点开始
        Node node=head;
        //因为是从头结点开始的，所以下面循环会找到i位置的前一个结点
        for(int index=0;index<i;index++){
            node=node.next;
        }
        //i位置处的结点
        Node iNode=node.next;
        //直接让i位置处的前以结点指向i位置的后一结点就可以删除i位置处的结点
        node.next=iNode.next;//或者也可以node.next=node.next.next;
        //元素减1
        N--;
        return iNode.item;
    }
    //方法8：查找元素t在链表中第一次出现的位置
    public int indexOf(T t){
        Node node=head;
        for(int index=0;node.next!=null;index++){
            node=node.next;
            if(node.item.equals(t)){
                return index;
            }

        }
        //找不到
        return -1;
    }
    //实现Iterable接口，重写iterator方法
    @Override
    //因为要的接口对象(接口不能直接new)，所以我们必须创建一个对象去实现这个接口
    public Iterator iterator() {
        return new LIterator()  ;
    }
    public class LIterator implements Iterator{
     //实现Iterator接口重写hasNext()和next()两个方法
        private Node n;
        public LIterator(){
            this.n=head;//从头结点开始
        }
        @Override
        public boolean hasNext() {//是否有元素
            return n.next!=null;
        }

        @Override
        public Object next() {//返回下一个元素
            n=n.next;
            return n.item;
        }
    }
}

测试类下：

public class LinkListText {
    public static void main(String[] args) {
        //创建链表对象
        LinkList<String> list=new LinkList<String>();
        list.insert("张三");
        list.insert("李四");
        list.insert("王五");
        list.insert("李四");
        System.out.println("链表为空吗："+list.isEmpty());
        for(Object s:list){
            System.out.println(s);
        }
        //元素个数
        System.out.println("初始元素个数："+list.length());
        System.out.println("----------------------");
        //插入
        list.insert(1,"赵六");
        list.insert(2,"历七");
        //元素个数
        System.out.println("插入后元素个数:"+list.length());
       //第一次出现的位置
        System.out.println("张三第一次出现的位置:"+list.indexOf("张三"));
        System.out.println("----------------------");
        for(Object s:list){
        System.out.println(s);
    }
        //清除链表
        list.clear();
        System.out.println("清除后，链表为空吗："+list.isEmpty());

    }
}

运行效果图： 

四、鲁迅说：一个是关于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