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

2021-07-12 01:56:30

 目录

一、前言

二、链表的简介

三、单向链表的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;
    }

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

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

//方法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++;
    }

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

 在指定i处，添加元素t

//方法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++;
    }

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

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

//方法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;
    }

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

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

//方法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接口

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一样的道理。

上一篇：[学习报告]《LeetCode零基础指南》(第五讲) 指针（上）


下一篇：【Java】斗地主和斗牛游戏