链表

作者: 觥筹啊觥筹 | 来源:发表于2019-04-27 21:15 被阅读1次

链表基础
双向链表&双向循环链表
算法与数据结构:链表
链表
五、双向链表
链表
数据与算法结构
数据结构——链表
链表
Algorithm小白入门 -- 单链表

链表

单链表反转

链表中环的检测

两个有序链表合并

删除链表倒数第n个节点

求链表的元素总个数

1556292316931.png

一.单向链表链表共有特征

单向链表,不循环,指针域只有后继指针

链表由多个元素块组成,上图为单向链表,每个元素块都由数据域 和 指针域,组成,单链的指针域存放指向下一节点的指针,也叫后继指针,理解为java中的地址引用; 双向链表指针域有前继指针****,和后继指针**;

一个链表中每个节点的地址都是不连续的,并且数据空间的大小不一致,而数组中每个数据空间的地址都是连续的,并且每个数组空间都有相同的容量;
- 连续地址: 内存中的一块连续的存储空间,空间地址为有序

如果内存还剩下500M,并且内存地址是不连续的,这时候申请一个200M的数组,如果内存中没有200M的连续的内存地址,则数组无法申请成功,但是若申请同大小的链表则可以;

头指针: 可以理解为java中的地址引用,头指针指向头节点,如果没有头节点,则直接指向首元节点,一个链表中必须存在头指针,头指针也可以冠名为该链表;
头节点: 头节点存在的意义主要是为了方便操作链表而设置的,如要删除和更换首元地址时,其本身不计算在链表的长度内,他的数据域一般不存储信息,链表中可以没有头节点,它的存在使操作链表方便;

有头节点的链表叫做带头链表,相反叫做不带头链表

头节点的内存地址直接被头指针引用,并且它的后继指针指向的节点叫做首元节点;
首元节点: 是链表中第一个存放有效数据的节点;

固定格式 : 头指针 -> [ 头节点] -> [首元节点]

线性结构通用接口

Java中,所以继承List接口的数据结构都有线性结构的特性



package linked;

/**
 * create by lyuweigh
 * date 2019 2019/4/26 20:57
 * description <>
 */

/**
 * 线性数据结构共有属性
 */
public interface List<E> {
    /**
     * 获取数组的长度
     * @return
     */
    int size();

    /**
     * 数组是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 插入一个元素
     * @param index
     * @param e
     * @throws Exception
     */
    void insert(int index, E e) throws Exception;

    /**
     * 删除一个元素
     * @param index
     * @throws Exception
     */
    void delete(int index)throws Exception;

    /**
     * 获取一个元素
     * @param index
     * @return
     * @throws Exception
     */
    Object get(int index)throws Exception;


}

单向链表代码实现

最灵魂的是index()方法,将要操作的节点设置为当前节点

package linked;

/**
 * create by lyuweigh
 * date 2019 2019/4/26 21:01
 * description <>
 */

public class LinkedList<E> implements List<E> {
    /**
     * 头指针,也就是头节点的引用
     * <p>
     * head(头指针) = 头节点.next = 首元节点.next = xxxx
     */
    private Node<E> head;

    /**
     * 当前节点对象
     */
    private Node<E> current;

    /**
     * 节点个数
     */
    private int size;


    /**
     * 初始化一个链表,并且头指针指向一个空的节点,这个节点就是头节点,他没有数据域
     * 直接指向,将头节点的内存地址复制给头指针,表明head指向头节点,而不是用next;头指针不是节点,他只是指针
     */
    public LinkedList() {
        this.head = current = new Node<E>(null);
        this.size = 0;
    }

    /**
     * 定位方法,定位到当前要被操作节点的前一个节点,然后操作该节点的next来决定是否要在被操作节点之前增加节点还是要删除要被操作的节点
     * <p>
     * 该方法直接定位到要操作节点的前一个节点身上
     * 比如 a->b->c->d->e->f->g  要删除e节点,则要定位到d节点的位置,就是将当前current定位到d 的位置
     * <p>
     * index 是 e 的位置
     *
     * @param index 下标
     */
    public void index(int index){
        /**
         * index < -1 :线性表中,起始数据位置为0,也就是首元节点的位置是0,那么头节点的位置就是-1,如果要操作首元节点,则需要定位到头节点的位置上
         *
         * index > this.size - 1 : 每增加一个元素,size就+1,size从头节点开始为0,但真实长度是从首元节点开始算的,所以在增加元素刚好是首元节点时,size=1,节点个数为1,实际可操作节点也就只有1个
         *
         * index+1 是e节点后面一个节点的位置,这里满足e节点为-1的情况, 和e节点为尾节点的情况 所以 这里的边界在 index=-1  ----- index = size 之间,
         */

        /**
         * 有多少可以定位到的节点?  头节点,首元节点  -> 尾节点   ( -1 -----  size) 否则越界
         */
        if (index + 1 < 0 || index + 1 > this.size) {
            throw new IndexOutOfBoundsException("链表索引越界");
        }

        /**
         * 如果要定位到头节点位置,则可以直接返回,因为构造里面本身就将当前位置设置为了头节点
         * PS: index如果为-1,那么当前节点的位置一定是头节点, 如果链表长度为4,则从首元链表开始  0 1 2 3 ,只有在操作首元的时候index才会等于-1,而每次增加数据,
         * current都会改变 @Method insert()
         */
        if (index == -1) {
            return;
        }
        /**
         * 当前节点先定位到首元节点的位置
         *  head是头指针,也就是头节点的引用
         */

        this.current = head.next;
        int j = 0;
        //首元节点不为null并且当前要操作的元素下标>0,大于0表示不把当前的首元节点包含在内
        while (current != null && j < index) {
            //\原本定位到了首元节点的位置0,如果不满足,就要定位到下标为1的位置,一直加,直到定位到index位置的元素的前一个元素位置而止
            this.current = current.next;
            j++;
        }


    }


    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
//        return head.next == null;
        return size == 0;
    }


    private void checkEmpty() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("链表索引越界");

        }
    }

    //在链表末尾添加一个元素
    public boolean add(E data) {
        if (data == null) return false;
        //要将当前元素定位到链表末尾,size-1 就是末尾的下标
        try {
            //直接定位到最后一个元素
            index(size - 1);
           // current.next = new Node<E>(data, null);
        } catch (Exception e) {
            e.printStackTrace();
            return false;
        }
        size++;
        return true;
    }


    /**
     * 插入?在哪插入,如 a->b->c->d->e->f->g  要在d的前面插入,则需要定位到c 则定位代码为index(index-1),若要在d的后面插入则为index(index)
     * 插入新元素,下标为index === 在index的位置插入新元素
     *
     * @param index
     * @param e
     * @throws Exception
     */
    @Override
    public void insert(int index, E e) {
        //最大可插入范围是{0~~~size} 0 到 最大下标+1的位置,
        //当前方法可以在最后一个节点的后面插入
        if (index < 0 || index > this.size-1) 
            throw new IndexOutOfBoundsException("链表索引越界");
        else if (index == size) add(e);//在最后一个位置插入,调用add方法

        index(index - 1);//在当前位置插入 如果有越界行为,index()方法不会允许的,index的范围是 0 ---- size
//        index(index);//在当前位置后面插入
        /**定位到前面index前面一个元素去了,
         * 新插入的元素叫做newnode
         * 当前元素就是 nownode
         * 所以结构应该是这样  node(index-1)->newnode(index)->nownode(index-1)
         */
        current.next = new Node(e, current.next);
        size++;
    }

    /**
     * 删除下标为index的元素
     *
     * @param index
     * @throws Exception
     */
    @Override
    public void delete(int index){
        checkEmpty();
        //范围区间{0,size-1(最大下标)}
        if (index < 0 || index > this.size-1) {
            throw new IndexOutOfBoundsException("链表索引越界");
        }
        index(index - 1);
        this.current.next = this.current.next.next;
        size--;
    }


    @Override
    public E get(int index) {
        try {
            if (index + 1 < 0 || index + 1 > this.size) {
                throw new Exception("链表索引越界");

            }
            index(index);
            return current.data;
        } catch (Exception e) {
            throw new RuntimeException("链表索引越界");
        }

    }


    class Node<E> {
        private E data;
        private Node<E> next;

        public Node(Node<E> next) {
            this.next = next;
        }

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }

    }

}

链表的时间复杂度

1. 插入/删除

16633923-dc1ee3981bf68018.png

图示,在链表中执行插入和删除操作,只需要改动两个元素的下一节元素的地址就就行,如果是双向链表,还需改动其上一节点地址,也就是进行两次地址改动操作,其消耗性能之差忽略不计.

但需要删除一个节点时,需要得到要被删除节点的上一节节点和下一节节点的信息,如果是单向链表,因为其内存地址不连续, 所以无法和数组一样通过下标和数组首地址进行寻址操作;链表想要获取到其上一节点的信息,就只能对链表进行遍历,得到当前节点位置或上一节结点位置,而遍历查询的时间复杂度为 $O(n)$ ,双向链表则没有这种情况,比起单向链表它多了空间,但是节省了时间;

小结: 单向链表删除操作的时间复杂度为 $T(n)=O(n)$ ;双向链表删除操作的复杂度为 $T(n)=O(1)$ ;只讲究单独的节点操作复杂度为T(n)=O(1);

2. 查询

链表执行查询,只能从一个起始地点开始根据每个节点中存储的下一节点地址信息进行遍历,如果要查询的节点在链表中n的位置,则需要遍历n次,所以其时间复杂度为: $T(n)=O(n)$

二.单向循环链表

循环链表和非循环链表

差别只在循环链表的尾节点指针域中存放这指向首元节点的指针

1556344523734.png

链表的最后一个节点指向首元节点

链表中在最后位置添加元素的方法是add(),只需将上文中的add()改成如下

    //在链表末尾添加一个元素
    public boolean add(E data) {
        if (data == null) return false;
        //要将当前元素定位到链表末尾,size-1 就是末尾的下标
        try {
            //直接定位到最后一个元素
            index(size - 1);
            //循环链表中,最后一个节点的下一节是首元节点
            current.next = new Node<E>(data, head.next);

        } catch (Exception e) {
            e.printStackTrace();
            return false;
        }
        size++;
        return true;
    }

三.双向链表

双向链表的删除操作相比来说比较复杂,其消耗的内存空间也比单向链表大,因为多了一个指针

但是双向链表大的可操作空间就很大,可以快读定位到附件节点

1556369882292.png

一个双向带头链表

      
    public LinkedListDouble() {
        this.head = current = new Node<E>(null);
        this.size = 0;
        this.head.pre = head;
        this.head.next = head;
    }



public void index(int index) {
        /**
         * index < -1 :线性表中,起始数据位置为0,也就是首元节点的位置是0,那么头节点的位置就是-1,如果要操作首元节点,则需要定位到头节点的位置上
         *
         * index > this.size - 1 : 每增加一个元素,size就+1,size从头节点开始为0,但真实长度是从首元节点开始算的,所以在增加元素刚好是首元节点时,size=1,节点个数为1,实际可操作节点也就只有1个
         *
         * index+1 是e节点后面一个节点的位置,这里满足e节点为-1的情况, 和e节点为尾节点的情况 所以 这里的边界在 index=-1  ----- index = size 之间,
         */

        /**
         * 有多少可以定位到的节点?  头节点,首元节点  -> 尾节点   ( -1 -----  size) 否则越界
         */
        if (index + 1 < 0 || index + 1 > this.size) {
            throw new IndexOutOfBoundsException("链表索引越界");
        }

        /**
         * 如果要定位到头节点位置,则可以直接返回,因为构造里面本身就将当前位置设置为了头节点
         * PS: index如果为-1,那么当前节点的位置一定是头节点, 如果链表长度为4,则从首元链表开始  0 1 2 3 ,只有在操作首元的时候index才会等于-1,而每次增加数据,
         * current都会改变 @Method insert()
         */
        if (index == -1) {
            current = head;
            return;
        }
        /**
         * 当前节点先定位到首元节点的位置
         *  head是头指针,也就是头节点的引用
         */

        this.current = head.next;
        int j = 0;
        //循环列表,current == head时表示当前数组没有元素
          
        while (current != head && j < index) {
            //\原本定位到了首元节点的位置0,如果不满足,就要定位到下标为1的位置,一直加,直到定位到index位置的元素的前一个元素位置而止
            this.current = current.next;
            j++;
        }


    }
    
    //在链表末尾添加一个元素
    public boolean add(E data) {
        if (data == null) return false;
        //要将当前元素定位到链表末尾,size-1 就是末尾的下标
        try {
            //直接定位到最后一个元素
            index(size - 1);

            if (size == 0) {
                Node<E> eNode = new Node<E>(this.current, data, head.next);
                eNode.pre = eNode.next = eNode;
                head.pre = head.next = eNode;
                size++;
                return true;
            }

            //双向循环链表插入一个元素  前面节点的下一个节点是新节点,新节点的上一个节点是当前节点,新节点的下一个接电视是节点
            head.next.pre = current.next =  new Node<E>(this.current, data, head.next);;

        } catch (Exception e) {
            e.printStackTrace();
            return false;
        }
        size++;
        return true;
    }


    /**
     * 插入?在哪插入,如 a->b->c->d->e->f->g  要在d的前面插入,则需要定位到c 则定位代码为index(index-1),若要在d的后面插入则为index(index)
     * 插入新元素,下标为index === 在index的位置插入新元素
     *
     * @param index
     * @param e
     * @throws Exception
     */
    @Override
    public void insert(int index, E e) {
        //最大可插入范围是{0~~~size} 0 到 最大下标+1的位置,
        //当前方法可以在最后一个节点的后面插入
        if (index < 0 || index > this.size)
            throw new IndexOutOfBoundsException("链表索引越界");
        else if (index == size) {
            add(e);
            return;
        }

        index(index - 1);//在当前位置插入 如果有越界行为,index()方法不会允许的,index的范围是 0 ---- size
//        index(index);//在当前位置后面插入
        /**定位到前面index前面一个元素去了,
         * 新插入的元素叫做newnode
         * 当前元素就是 nownode
         * 所以结构应该是这样  node(index-1)->newnode(index)->nownode(index-1)
         */

        current.next = current.next.pre = new Node(this.current, e, current.next);

        size++;
    }
    /**
     * 删除下标为index的元素
     *
     * @param index
     * @throws Exception
     */
    @Override
    public void delete(int index) {
        checkEmpty();
        //范围区间{0,size-1(最大下标)}
        if (index < 0 || index > this.size - 1) {
            throw new IndexOutOfBoundsException("链表索引越界");
        }
        index(index - 1);
        //要操作节点的前一个节点的后一个节点的后一个节点的前一个节点值为当前节点,直接忽略掉要被删除的节点
        this.current.next.next.pre = this.current;
        //要操作节点的上一个节点的下一个节点是要被删除节点的下一个节点,也是直接忽略掉要被删除的节点
        this.current.next = this.current.next.next;

        size--;
    }

链表基础
链表基础链表长度链表为空链表结构链表增加
双向链表&双向循环链表
链表分为：单链表、单向循环链表、双向链表、双向循环链表本节主要说明：双向链表、双向循环链表定义结点一、双向链表...
算法与数据结构:链表
链表链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...
链表
链表单链表反转链表中环的检测两个有序链表合并删除链表倒数第n个节点求链表的元素总个数一.单向链表链表共有特征...
五、双向链表
双向链表此前介绍的链表，也叫做单向链表使用双向链表可以提升链表的综合性能修改之前的单链表的源码：双向链表 –...
链表
内容链表数据结构向链表添加元素从链表移除元素使用 LinkedList 表双向链表循环链表链表数据结...
数据与算法结构
线性表顺序表链表（物理上离散，逻辑上连续）链表的类别单链表循环链表双链表链表的操作顺序表与链表的比...
数据结构——链表
本文所讲的链表是单链表，链表采用无头链表科普下：一般链表可以分为有头节点的链表与无头节点的链表有头节点的链表：...
链表
文章结构链表的定义链表的插入和删除操作链表的特性常见的链表结构自定义链表链表的经典操作使用链表实现L...
Algorithm小白入门 -- 单链表
单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表单链表节点的结构如下： 1.1 递归反转整个单链表...

链表

链表

一.单向链表链表共有特征

线性结构通用接口

单向链表代码实现

链表的时间复杂度

1. 插入/删除

2. 查询

二.单向循环链表

循环链表和非循环链表

三.双向链表

相关文章

链表基础

双向链表&双向循环链表

算法与数据结构:链表

链表

五、双向链表

链表

数据与算法结构

数据结构——链表

链表

Algorithm小白入门 -- 单链表

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法与数据结构

数据结构和算法分析

链表

链表

一.单向链表 链表共有特征

线性结构通用接口

单向链表代码实现

链表的时间复杂度

1. 插入/删除

2. 查询

二.单向循环链表

循环链表和非循环链表

三.双向链表

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

一.单向链表链表共有特征