java数据结构线性表之链表(代码片段)

（1）链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元 素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成， 结点可以在运行时动态生成。

那我们如何使用链表呢？按照面向对象的思想，我们可以设计一个类，来描述结点这个事物，用一个属性描述这个 结点存储的元素，用来另外一个属性描述这个结点的下一个结点。

结点API设计：

结点类实现：

/**
 * 节点类实现
 */
public static class Node<T>
    // 存储元素
    public T item;
    // 指向下一个节点
    public Node<T> next;

    public Node(T item,Node<T> next)
        this.item = item;
        this.next = next;
    

生成链表：

public static void main(String[] args) throws Exception  
	//构建结点 
	Node<Integer> first = new Node<Integer>(11, null); 
	Node<Integer> second = new Node<Integer>(13, null); 
	Node<Integer> third = new Node<Integer>(12, null); 
	Node<Integer> fourth = new Node<Integer>(8, null); 
	Node<Integer> fifth = new Node<Integer>(9, null);

	//生成链表 
	first.next = second; 
	second.next = third; 
	third.next = fourth; 
	fourth.next = fifth;

（2）单向链表

单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据， 指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。

（2.1）单向链表API设计

（2.2）单向链表代码实现

package cn.itcast.algorithm.linear;

import java.util.Iterator;

/**
 * @author ：caizhengjie
 * @description：单向链表
 * @date ：2021/6/28 10:59 下午
 */
public class LinkList<T> implements Iterable<T>

    /**
     * 记录头节点
     */
    private Node<T> head;

    /**
     * 记录链表的长度
     */
    private int N;

    /**
     * 节点类实现
     */
    public static class Node<T>
        // 存储元素
        public T item;
        // 指向下一个节点
        public Node<T> next;

        public Node(T item,Node<T> next)
            this.item = item;
            this.next = next;
        
    

    /**
     * 构造方法
     */
    public LinkList() 
        // 初始化头节点
        this.head = new Node<>(null, null);
        // 初始化元素个数
        this.N = 0;
    

    public LinkList(Node<T> head, int n) 
        this.head = head;
        N = n;
    
    /**
     * 置空链表
     */
    public void clear()
        // 让头节点为null
        head.next = null;
        // 让元素个数为0
        this.N = 0;
    

    /**
     * 判断链表是否为空，是返回true，否则返回false
     */
    public boolean isEmpty()
        // 只需判断元素个数是否为0，为0就是空，不为0就不是空
        return N == 0;
    

    /**
     * 获取链表中元素的个数
     */
    public int length()

        return N;
    

    /**
     * 读取并返回链表中第i个元素
     */
    public T get(int i)
         // 通过循环从头节点开始往后找，依次找i次，就可以找到对应的元素
        Node<T> n = head.next;
        for (int index = 0;index < i;index++)
            n = n.next;
        
        return n.item;
    

    /**
     * 删除并返回链表中第i个元素的个数
     */
    public T remove(int i)

        // 找到i位置的前一个节点
        Node<T> pre = head;
        for (int index = 0;index <= i-1;index++)
            pre = pre.next;
        

        // 找到i位置的节点
        Node<T> curr = pre.next;

        // 找到i位置的下一个节点
        Node<T> nextNode = curr.next;

        // 前一个节点指向下一个节点
        pre.next = nextNode;

        // 元素个数-1
        N--;
        return curr.item;

    

    /**
     * 往链表中添加一个元素
     */
    public void insert(T t)
        // 找到当前最后一个节点
        Node<T> n = head;
        while (n.next != null)
            n = n.next;
        

        // 创建新节点，保存元素t
       Node<T> newNode =  new Node<T>(t,null);

        // 让当前最后一个节点指向新节点
        n.next = newNode;

        // 元素的个数+1
        N++;

    

    /**
     * 在链表的第i个元素之前插入一个值为t的数据元素
     */
    public void insert(int i,T t)
        // 找到i位置前一个节点
        Node<T> pre = head;
        for (int index = 0;index <= i-1;index++)
            pre = pre.next;
        

        // 找到i位置的节点
        Node<T> curr = pre.next;

        // 创建新节点，并且新节点需要指向原来i位置的节点
        Node<T> nowNode = new Node<>(t,curr);

        // 原来i位置的前一个节点指向新节点即可
        pre.next = nowNode;

        // 元素个数+1
        N++;

    

    /**
     * 返回链表中首次出现的指定的数据元素的位序号，若不存在，则 返回-1。
     */
    public int indexOf(T t)

        // 从头节点开始，依次找到每个节点，取出item，和t比较，如果相同，就找到了
        Node<T> n = head;
        for (int i = 0;n.next != null;i++)
            n = n.next;
            if (n.item.equals(t))
                return i;
            
        
        return -1;
    

    /**
     * 链表反转
     * 反转整个链表
     * @return
     */
    public void reverse()
        // 判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
        if (isEmpty())
            return;
        
        reverse(head.next);

    


    /**
     * 反转指定的节点curr，并把反转后的节点返回
     * @return
     */
    public Node<T> reverse(Node<T> curr)
        if (curr.next == null)
            head.next = curr;
            return curr;
        
        // 递归的反转当前节点curr的下一个节点；返回值就是链表反转后当前节点的上一个节点
        Node<T> pre = reverse(curr.next);

        // 让返回的节点的下一个节点变为当前节点curr
        pre.next = curr;

        // 把当前节点的下一个节点变为null
        curr.next = null;
        return curr;
    

    @Override
    public Iterator iterator() 
        return new LTterator();
    

    private class LTterator implements Iterator
        private Node<T> n;

        public LTterator() 
            this.n = head;
        

        @Override
        public boolean hasNext() 
            return n.next != null;
        

        @Override
        public Object next() 
            n = n.next;
            return n.item;
        
    

测试代码：

package cn.itcast.algorithm.test;

import cn.itcast.algorithm.linear.LinkList;


/**
 * @author ：caizhengjie
 * @description：TODO
 * @date ：2021/2/2 12:11 上午
 */
public class LinkListTest 
    public static void main(String[] args) 
        // 创建单向链表对象
        LinkList<String> l1 = new LinkList<>();

        // 测试插入
        l1.insert("alex");
        l1.insert("lili");
        l1.insert("jone");
        l1.insert(1,"jack");

        // 遍历
        for (String s : l1) 
            System.out.println(s);
        

        // 测试获取
        String getResult = l1.get(1);
        System.out.println("获取索引1处的结果为：" + getResult);

        // 测试删除
        String removeResult = l1.remove(0);
        System.out.println("删除的元素为：" + removeResult);

        // 测试清空
        l1.clear();
        System.out.println("清空后线性表中的元素的个数为：" + l1.length());
    

alex
jack
lili
jone
获取索引1处的结果为：jack
删除的元素为：alex
清空后线性表中的元素的个数为：0

（3）双向链表

双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用 来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存 储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。

按照面向对象的思想，我们需要设计一个类，来描述结点这个事物。由于结点是属于链表的，所以我们把结点类作 为链表类的一个内部类来实现

（3.1）结点API设计

（3.2）双向链表API设计

（3.3）双向链表代码实现

package cn.itcast.algorithm.linear;

import java.util.Iterator;

/**
 * @author ：caizhengjie
 * @description：双向链表
 * @date ：2021/7/6 11:44 下午
 */
public class TowWayLinkList<T> implements Iterable<T>

    /**
     * 记录头节点
     */
    private Node<T> head;

    /**
     * 记录尾节点
     */
    private Node<T> last;

    /**
     * 记录链表的长度
     */
    private int N;

    /**
     * 节点类实现
     */
    public static class Node<T>
        // 存储元素
        public T item;
        // 指向下一个节点
        public Node<T> next;
        // 指向上一个节点
        public Node<T> pre;

        public Node(T item, Node<T> pre,Node<T> next)
            this.item = item;
            this.pre = pre;
            this.next = next;
        
    

    /**
     * 构造方法
     */
    public TowWayLinkList() 
        // 初始化头节点和尾节点
        this.head = new Node<>(null,null,null);
        // 初始化元素个数
        this.N = 0;

    

    /**
     * 置空链表
     */
    public void clear()
        // 让头节点和尾节点为null
        this.head.next = null;
        this.head.pre = null;
        this.head.item = null;
        this.last = null;

        // 让元素个数为0
        this.N = 0;
    

    /**
     * 判断链表是否为空，是返回true，否则返回false
     */
    public boolean isEmpty()
        // 只需判断元素个数是否为0，为0就是空，不为0就不是空
        return N == 0;
    

    /**
     * 获取链表中元素的个数
     */
    public int length()

        return N;
    


    /**
     * 获取第一个元素
     */
    public T getFirst()
        if (isEmpty())
            return null;
        
        return head.next.item;
    

    /**
     * 获取最后一个元素
     */
    public T getLast()
        if (isEmpty())
            return null;
        
        return last.item;
    

    /**
     * 插入元素t
     */
    public void insert(T t)
        // 如果链表为空
        if (isEmpty())
            // 创建新的节点
            Node<T> newNode = new Node<T>(t,head,null);
            // 让新节点称为尾节点
            last = newNode;
            // 让头节点指向尾节点
            head.next = last;

        

        // 如果链表不为空
        else 
            // 当前尾节点
            Node<T> oldLast = last;
            // 创建新的节点
            Node<T> newNode = new Node<T>(t,oldLast,null);
            // 让当前的尾节点指向新节点
            oldLast.next = newNode;
            //  让新节点成为尾节点
            last = newNode;

        

        // 元素个数+1
        N++;
    

    /**
     * 在链表的第i个元素之前插入一个值为t的数据元素
     */
    public void insert(int i,T t)
        // 找到i位置的前一个节点
        Node<T> pre = head;
        for (int index = 0;index < i; index++)
            pre = pre.next;
        

        // 找到i位置的节点
        Node<T> curr = pre.next;

        // 创建新节点
        Node<T查看详情  

                
03线性表之链表(代码片段)
肚子饿了就要吃  ~  嗝 ———路飞 1.本章重点链表表示和实现（单链表+双链表）链表的常见OJ题顺序表和链表的区别和联系2.为什么需要链表引子：顺序表的问题及思考(1)动态顺序表特点：插入数据，...  查看详情  
                
c语言严蔚敏数据结构线性表之链表实现(代码片段)
...近在考成都大学皇家计算机科学与技术专业，复习专业课数据结构，正好学习到线性结构中的线性表用链表这种存储结构来实现。　　首先，数据结构包括1、数据的操作2、逻辑结构3、存储结构(数据结构三要素。　　直接上代...  查看详情  
                
数据结构学习笔记二线性表之链表篇（双向链表）(代码片段)
链表根据带头不带头、单向或双向、循环非循环三个方面可组成成八种类型。这八种类型中仅有两种是我们常用的。第一种是单向不带头非循环链表，也就是单链表。单链表因为结构简单，但是实际操作比较复杂，所...  查看详情  
                
线性表之链表(代码片段)
...一个数据元素。对于非线性的链表:可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn），和平衡二叉树一样。其中存储数据元素信...  查看详情  
                
线性表之链表c语言
线性表之链表【C语言】2.5线性表的链式表示和实现4、头指针、头结点和首元结点:讨论1:如何表示空表?讨论2:在链表中设置头结点有什么好处?讨论3:头结点的数据域内装的是什么?■链表(链式存储结构)的特点2.5.1单链表的定义和...  查看详情  
                
线性表之链表源码
//链表#include<iostream>#include<algorithm>usingnamespacestd;typedefstructLNode{	intdata;	structLNode*next;}LNode,*LinkList;intInitList_L(LinkList&L){	L=newLNode;	L->next=NULL;	return  查看详情  
                
数据结构线性表之实现单循环链表(代码片段)
数据结构线性表之实现单循环链表数据结构线性表之实现单循环链表相关文章单循环链表单循环链表定义数据结构线性表之实现单循环链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实...  查看详情  
                
数据结构(线性表之单链表)(代码片段)
文章目录🥇为何要使用链表🥇单链表是什么单链表的数据存储方式🥇单链表之创建链表🥇单链表之打印链表🥇单链表之计算链表长度🥇单链表之增删查改单链表之头插法单链表之尾插法单链表之把一个...  查看详情  
                
数据结构与算法-线性表之双向链表(代码片段)
参考博客：http://www.cnblogs.com/skywang12345/p/3561803.htmlhttps://blog.csdn.net/howlaa/article/details/385132351、概述线性表是一种线性结构，由数组、单项链表和双向链表组成，这里讲讨论双向链表的理论知识和实现代码。双向链表和单项链表类...  查看详情  
                
数据结构线性表之实现单链表(代码片段)
数据结构线性表之实现单链表数据结构线性表之实现单链表相关文章单链表定义单链表相关操作数据结构线性表之实现单链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实现顺序表(三)数...  查看详情  
                
数据结构与算法-线性表之静态链表(代码片段)
...针，那么在没有引用或指针的语言中，该怎么实现这个的数据结构呢？一、简介　　定义：用数组代替指针或引用来描述单链表，即用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法；　　上面的静态链表图有两个...  查看详情  
                
数据结构学习总结线性表之单链表(代码片段)
   一，回忆链表 　链表，别名链式存储结构或单链表，用于存储逻辑关系为"一对一"的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。&nbs...  查看详情  
                
数据结构之链表及实现(代码片段)
线性表的链式表示和实现线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。正由于这种特点，在做插入和删除操作时，需移动大量元素。链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，...  查看详情  
                
数据结构与算法(java)之链表(代码片段)
单向链表packagecom.weeks.linkedlist;importjava.util.Stack;/***@author达少*@version1.0*实现链表，保存水浒传英雄人物*/publicclassLinkedListDemopublicstaticvoidmain(String[]args)//创建英雄任务HeroNodehero1=ne  查看详情  
                
数据结构线性表之顺序表arraylist(代码片段)
...ArrayList。为什么我们称其为顺序表呢？原因顾名思义是该数据结构在逻辑上和物理结构上的存储顺序均是连续的。下面，我们就以一张图来说明什么是顺序表。 这个图代表逻辑上的9个元素，每一个位置均存储一个数据，数...  查看详情  
                
算法习题---线性表之单链表的查找(代码片段)
一：问题已知一个带头结点的单链表，结点结构为（data，link）假设该链表只给出了头指针list，在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该...  查看详情  
                
数据结构与算法-线性表之循环链表(代码片段)
前言：前面几篇介绍了线性表的顺序和链式存储结构，其中链式存储结构为单向链表（即一个方向的有限长度、不循环的链表），对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说...  查看详情