数据结构——链表

作者 : 开心源码 本文共10572个字,预计阅读时间需要27分钟 发布时间: 2022-05-11 共116人阅读

目录

1、属性

2、链表和数组的区别

2.1、数组概述

2.2、数组和链表优缺点

2.3、链表和数组的比较

3、单向链表

3.1、单向链表的基本操作

3.1.1、链表的遍历
3.1.2、链表的插入
3.1.2.1、在单向链表的开头插入结点
3.1.2.2、在单向链表的结尾插入结点
3.1.2.3、在单向链表的中间插入结点
3.1.2.4、函数实现
3.1.3、链表的删除
3.1.3.1、删除链表的表头
3.1.3.2、删除链表的表尾
3.1.3.3、删除链表中间的结点
3.1.3.4、函数实现
3.1.4、链表的释放

4、双向链表

4.1、双向链表的插入

4.1.1、在双向链表的开头插入结点
4.1.2、在双向链表的末尾插入结点
4.1.3、在双向链表的中间插入一个结点
4.1.4、函数实现

4.2、双向链表的删除

4.2.1、删除双向链表的第一个结点
4.2.2、删除双向链表的最后一个结点
4.2.3、删除双向链表中间的一个结点
4.2.4、代码实现

5、循环链表

5.1、遍历循环链表

5.2、在循环链表的表尾插入结点

5.3、在循环链表的表头插入结点

5.4、删除循环链表中的最后一个结点

5.5、删除循环链表中的第一个结点

6、松散链表

6.1、在松散链表查找一个元素

6.2、在松散链表中插入一个元素

6.3、在松散链表中执行移动操作

正文

1、属性

①:相邻元素之间通过指针连接。
②:最后一个元素的后继指针为NULL。
③:链表的空间可以够按需分配。
④:没有内存空间的白费。

图1-1 链表示用意

2、链表和数组的区别

链表和数组都能使用于存储数据集合,因为两者的使用途相同,所以需要对它们的使用法进行区分。

2.1、数组概述

整个数组所有元素存储在操作系统分配的一个内存块中,通过用特定元素的索引作为数组下标,能在常数时间内访问数组元素。

图2-1 数组示用意

2.2、数组和链表优缺点

  • 数组的优点:
    1、简单且易使用 。
    2、访问元素为常数时间。
  • 数组的缺点:
    1、大小固定,在用数组前需要指定数组大小。
    2、需要分配一个连续空间块,当数组规模过大时,就无法分配存储整个数组的内存空间。
    3、假如要在数组中插入元素,可可以需要移动存储在数组中的其余元素,这样才可以腾出指定的位置来放插入的元素。
  • 链表的优点:
    1、链表能在常数时间内扩展。
    2、容易增加新元素。
  • 链表的缺点:
    1、访问单个元素的时间开销问题过大。
    2、有时很难对链表操作,假如要删除最后一项,倒数第二项必需更改后继指针为NULL。这需要从头遍历链表,找到倒数第二个结点的链接,并设置其后置指针为NULL。
    3、链表中的额外指针引使用需要白费内存。

2.3、链表和数组的比较

参数链表数组
索引O(n)O(1)
在最前台插入/删除O(1)O(n),假如数组空间没有填满(需要移动元素)
在最末端插入O(n)O(1),假如数组空间没有填满
在最末端删除O(n)O(1)
在中间插入O(n)O(n),假如数组空间没有填满(需要移动元素)
在中间删除O(n)O(n) ,假如数组空间没有填满(需要移动元素)
空间白费O(n)0

3、单向链表

链表通常是指单向链表,它包含多个结点,每个结点都有一个指向后继元素的next(下一个)指针。表中最后一个结点的next值为NULL,表示链表的结束。

图3-1 单向链表

下面是单向链表的类型公告:

public class ListNode {    private int data;    private ListNode next;    public ListNode(int data){        this.data=data;    }    public void setData(int data){        this.data=data;    }    public int getData(){        return data;    }    public void setNext(ListNode next){        this.next=next;    }    public ListNode getNext() {        return next;    }}

3.1、单向链表的基本操作

  • 遍历链表。
  • 在链表中插入一个元素。
  • 从链表中删除一个元素。
  • 删除链表。
3.1.1、链表的遍历

假设表头结点的指针指向链表中的第一个结点。遍历链表需要完成以下步骤:

  • 沿指针遍历。
  • 遍历时显示结点的内容。
  • 当next指针为NULL时结束遍历。

下面是遍历函数的公告:

    public int ListLength(ListNode headNode){        int length=0;        ListNode currentNode=headNode;        while (currentNode!=null){            length++;            System.out.print(currentNode.getData());            currentNode=currentNode.getNext();        }        return length;    }
3.1.2、链表的插入
3.1.2.1、在单向链表的开头插入结点

若要在当前表头结点前插入一个新结点,只要要修改一个next指针(新结点的next指针),如下步骤:

  • 升级新结点的next指针,使其指向当前的表头结点。

    图3-2 升级新结点

  • 升级表头指针的值,使其指向新结点。

    图3-3 升级表头指针

3.1.2.2、在单向链表的结尾插入结点

若要在表尾后插入一个新结点,则需要修改两个next指针(最后一个结点的next指针和新结点的next指针),如下步骤:

  • 新结点的next指针指向NULL。

    图3-4 升级新结点

  • 最后一个结点的next指针指向新结点。

    图3-5 升级表尾结点

3.1.2.3、在单向链表的中间插入结点

假设在这种情况下插入新结点,则需要修改两个next指针,如下步骤:

  • 假如要在位置3添加一个元素,则首先要将指针定位在链表的位置2。即需要从表头开始经过两个结点,而后插入新结点。为了简单起见,假设第二个结点为位置结点,新结点的next指针指向位置结点的下一个结点。

    图3-6 升级新结点

  • 位置结点的next指针指向新结点。

    图3-7 升级位置结点

3.1.2.4、函数实现
    ListNode InsertInLinkedList(ListNode headNode,ListNode nodeToInsert,int position){        if(headNode==null){            return headNode;        }        //求链表长度        int size=ListLength(headNode);        if(position>size+1||position<1){            System.out.print("position 的范围在1-(size+1)");            return headNode;        }        if(position==1){            //在链表开头插入            nodeToInsert.setNext(headNode);            return nodeToInsert;        }        else {            //在链表中间或者者末尾插入            //位置结点            ListNode previousNode=headNode;            int count=1;            while (count<position-1){                previousNode=headNode.getNext();                count++;            }            //位置结点的下一结点            ListNode currentNode=previousNode.getNext();            //升级新结点            nodeToInsert.setNext(currentNode);            //升级位置结点            previousNode.setNext(nodeToInsert);        }        return headNode;    }
3.1.3、链表的删除
3.1.3.1、删除链表的表头
  • 创立一个临时结点,它指向表头指针所指向的结点。

    图3-8 创立临时结点

  • 修改表头指针的值,使其指向下一个结点,并移除临时结点。

    图3-9 修改表头并移除临时结点

3.1.3.2、删除链表的表尾

该操作比删除链表的第一个结点要略微复杂少量,由于算法需要找到表尾结点的前驱结点。分三步实现:

  • 遍历链表,在遍历时还要保存前驱结点的地址,当遍历到链表的表尾时,将有两个指针,分别是表尾结点的指针和指向表尾结点的前驱结点的指针。

    图3-10 表尾及前驱结点

  • 将表尾的前驱结点的next指针升级为NULL。

    图3-11 升级前驱结点

  • 移除表尾结点

    图3-12 移除表尾

3.1.3.3、删除链表中间的结点

这种情况下,被删除的结点总是位于两个结点之间,因而不需要升级表头和表尾的指针。分两步实现:

  • 遍历链表,在遍历时保存前驱结点的地址,一旦找到被删除的结点,将前驱结点的next指针的值升级为被删除的结点的next指针的值。

    图3-13 升级前驱结点

  • 移除需删除的当前结点

    图3-14 移除结点

3.1.3.4、函数实现
ListNode DeleteNodeFromLinkedList(ListNode headNode,int position){        //求链表长度        int size=ListLength(headNode);        if(position>size||position<1){            System.out.print("position 的范围在1-size");            return headNode;        }        if(position==1){            //删除表头            ListNode currentNode=headNode.getNext();            headNode=null;            return currentNode;        }else {            //删除中间或者表尾            //前驱结点            ListNode previousNode=headNode;            int count=1;            while(count<position-1){                previousNode=previousNode.getNext();                count++;            }            //要删除的结点            ListNode currentNode=previousNode.getNext();            //升级前驱结点            previousNode.setNext(currentNode.getNext());            //删除当前结点            currentNode=null;        }        return headNode;    }
3.1.4、链表的释放

这个操作通过将当前结点存储在临时变量中,而后释放当前结点。当释放完当前结点后,移动到下一个结点并将其存储在临时变量中,而后不断重复该过程直至释放所有结点。代码如下:

    void DeleteLinkedList(ListNode headNode){        //临时变量 和 迭代器        ListNode tempNode,iterator=headNode;        while (iterator!=null){            tempNode=iterator.getNext();            iterator=null;            iterator=tempNode;        }    }

4、双向链表

  • 双向链表的优点:对于链表中一个给定的结点,能从两个方向进行操作。
  • 双向链表的缺点:每个结点需要一个额外的指针,因而需要更多的开销,插入和删除时更费时。

下面给出双向链表的类型公告:

public class DLLNode {    private int data;    private  DLLNode previous;    private  DLLNode next;    public DLLNode(int data){        this.data=data;    }    public void setData(int data) {        this.data = data;    }    public int getData() {        return data;    }    public void setPrevious(DLLNode previous) {        this.previous = previous;    }    public DLLNode getPrevious() {        return previous;    }    public void setNext(DLLNode next) {        this.next = next;    }    public DLLNode getNext() {        return next;    }}

4.1、双向链表的插入

分为以下三种情况:

  • 在链表的开头前插入一个新结点。
  • 在链表的末尾后插入一个新结点。
  • 在链表的中间插入一个新结点。
4.1.1、在双向链表的开头插入结点
  • 将新结点的后继指针升级为指向当前的表头结点,将前驱指针赋值为NULL。

    图4-1 升级新结点

  • 将表头结点的前驱指针升级为指向新结点,而后将新结点作为表头。

    图4-2 升级表头

4.1.2、在双向链表的末尾插入结点

这种情况下需要遍历到链表的最后,而后插入新结点。

  • 将新结点的后继指针赋值为NULL,前驱指针指向表尾结点。

    图4-3 升级新结点

  • 将表尾结点的后继指针升级为指向新结点。

    图4-4 升级表尾结点

4.1.3、在双向链表的中间插入一个结点
  • 将新结点的后继指针赋值为位置结点的后继结点,前驱指针指向位置结点。

    图4-5 升级新结点

  • 将位置结点的后继结点的前驱指针赋值为新结点,将位置结点的后继指针赋值为新结点。

    图4-6 升级位置结点、后继结点

4.1.4、函数实现
public DLLNode DLLInsert(DLLNode headNode,DLLNode nodeToInsert,int position){        if(headNode==null){            return nodeToInsert;        }        //求链表长度        int size=ListLength(headNode);        if(position<1||position>size+1){            System.out.print("position 的范围在1-(size+1)");            return headNode;        }        if(position==1){            //在链表开头插入            nodeToInsert.setNext(headNode);            headNode.setPrevious(nodeToInsert);            return nodeToInsert;        }else {            //在链表中间或者者表尾插入            //位置结点            DLLNode previousNode=headNode;            int count=1;            while (count<position-1){                previousNode=previousNode.getNext();                count++;            }            //位置结点的后继结点            DLLNode currentNode=previousNode.getNext();            //升级新结点            nodeToInsert.setNext(currentNode);            nodeToInsert.setPrevious(previousNode);            //升级位置结点            previousNode.setNext(nodeToInsert);            //升级位置结点的后继结点            if(currentNode!=null){                currentNode.setPrevious(nodeToInsert);            }        }        return headNode;    }

4.2、双向链表的删除

分为以下三种情况:

  • 删除链表的表头。
  • 删除链表的表尾。
  • 删除链表中间的一个结点。
4.2.1、删除双向链表的第一个结点
  • 创立一个临时结点,它与表头指向同一个结点。

    图4-7 临时结点

  • 修改表头指针,使其指向下一个结点,将表头指针的前驱指针赋值为NULL,而后移除临时结点。

    图4-8 升级表头、移除临时结点

4.2.2、删除双向链表的最后一个结点

需要找到表尾结点的前驱结点,分以下三步进行:

  • 遍历链表,同时保存前驱结点的地址。当遍历到表尾时,有两个指针分别是指向表尾结点的指针和指向表尾结点的前驱结点的指针。

    图4-9 表尾结点、表尾结点的前驱结点

  • 升级表尾结点的前驱结点的后继指针的值为NULL。

    图4-10 升级表尾结点的前驱结点

  • 移除表尾结点。

    图4-11 移除表尾结点

4.2.3、删除双向链表中间的一个结点
  • 与一种删除情况相似,在遍历链表时保存前驱结点。一旦找到要删除的结点,更改前驱结点的后继指针使其指向被删除结点的后继结点,更改被删除结点的后继结点的前驱指针指向被删除结点的前驱结点。

    图4-12 升级删除结点的前驱结点和后继结点

  • 移除被删除的当前结点。

    图4-13 删除结点

4.2.4、代码实现
public DLLNode DLLDelete(DLLNode headNode,int position){        int size=ListLength(headNode);        if(position<1||position>size){            System.out.print("position 的范围在1-size");            return headNode;        }        if(position==1){            //删除链表的第一个结点            DLLNode currentNode=headNode.getNext();            currentNode.setPrevious(null);            headNode=null;            return currentNode;        }else {            //删除链表的中间结点或者者最后一个结点            //前驱结点            DLLNode previousNode=headNode;            int count=1;            while(count<position-1){                previousNode=previousNode.getNext();                count++;            }            //删除结点            DLLNode currentNode=previousNode.getNext();            //后继结点            DLLNode laterNode=currentNode.getNext();            //升级前驱结点            previousNode.setNext(laterNode);            //升级后继结点            if(laterNode!=null){                laterNode.setPrevious(previousNode);            }            currentNode=null;        }        return headNode;    }

5、循环链表

在单向链表和双向链表中,都采使用NULL值作为链表的结束。然而循环链表没有结束标志。下面给出循环链表的类型公告:

public class CLLNode {    private int data;    private CLLNode next;    public CLLNode(int data){        this.data=data;    }    public void setData(int data) {        this.data = data;    }    public int getData() {        return data;    }    public void setNext(CLLNode next) {        this.next = next;    }    public CLLNode getNext() {        return next;    }}

5.1、遍历循环链表

循环链表能通过标记为表头的结点进行访问,从标记为表头的结点开始遍历,利使用虚拟结点——当前结点,当当前结点再次达到开始结点时结束遍历。代码实现如下:

 public int CircularListLength(CLLNode headNode){        int length=0;        CLLNode currentNode=headNode;        while (currentNode!=null){            length++;            currentNode=currentNode.getNext();            if(currentNode==headNode){                break;            }        }        return length;    }

5.2、在循环链表的表尾插入结点

在由表头开始的循环链表的表尾后插入一个新结点,也就是在表尾结点和第一个结点之间插入该新结点。

  • 创立一个新结点,并且初始化其next指针指向该结点自身。

    图5-1 创立新结点

  • 升级新结点的next指针为表头结点,而后循环遍历链表直至表尾。即插入位置应为循环链表中下一个结点是表头结点的结点位置。

    图5-2 升级新结点

  • 升级表头结点的前驱结点的next指针指向新结点。

    图5-3 升级表头的前驱结点

  • 代码实现:
 public void InsertAtEndInCLL(CLLNode headNode,CLLNode nodeToInsert){        CLLNode currentNode=headNode;        while (currentNode.getNext()!=headNode){            currentNode=currentNode.getNext();        }        //初始化        nodeToInsert.setNext(nodeToInsert);        if(headNode==null){            headNode=nodeToInsert;        }        else {            //升级新结点            nodeToInsert.setNext(headNode);            //升级表头的前驱结点            currentNode.setNext(nodeToInsert);        }    }

5.3、在循环链表的表头插入结点

与上述表尾后插入结点的唯一区别是,在插入新结点后,还需要升级指针。

  • 创立一个新结点,并且初始化其next指针指向该结点自身。

    图5-4 创立新结点

  • 升级新结点的next指针为表头结点,而后循环遍历链表直至表尾。即插入位置应为循环链表中下一个结点是表头结点的结点位置。

    图5-5 升级新结点

  • 升级表头结点的前驱结点的next指针指向新结点。

    图5-6 升级表头的前驱结点

  • 设置新结点为表头结点。

    图5-7 设置新结点为表头

  • 代码实现:

 public void InsertAtBeginInCLL(CLLNode headNode,CLLNode nodeToInsert){        CLLNode currentNode=headNode;        while (currentNode.getNext()!=headNode){            currentNode=currentNode.getNext();        }        //初始化        nodeToInsert.setNext(nodeToInsert);        if(headNode==null){            headNode=nodeToInsert;        }        else {            //升级新结点            nodeToInsert.setNext(headNode);            //升级表头的前驱结点            currentNode.setNext(nodeToInsert);            //设置新结点为表头            headNode=nodeToInsert;        }    }

5.4、删除循环链表中的最后一个结点

为了删除最后一个结点,需要遍历循环链表找到倒数第二个结点。该结点成为了新的表尾结点,其next指针指向第一个结点。

  • 遍历循环链表,找到表尾结点及其前驱结点。

    图5-8 遍历循环链表

  • 升级表尾结点的前驱结点的next指针,使其指向表头结点。

    图5-9 升级表尾结点的前驱结点

  • 移除表尾结点。

    图5-10 移除表尾结点

  • 代码实现:

public void DeleteLastNodeFromCLL(CLLNode headNode){        //表尾的前驱结点        CLLNode temp=headNode;        //表尾        CLLNode currentNode=headNode;        if(headNode==null){            System.out.print("List is empty");            return;        }        while (currentNode.getNext()!=headNode){            temp=currentNode;            currentNode=currentNode.getNext();        }        //升级表尾的前驱结点        temp.setNext(headNode);        //移除表尾        currentNode=null;        return;    }

5.5、删除循环链表中的第一个结点

只要要将表尾结点的next指针指向第一个结点的后继结点。

  • 遍历循环链表找到表尾结点,就是要删除结点的前驱结点。

    图5-11 遍历循环链表

  • 创立一个指向表头结点的临时结点,升级表尾结点的next指针,使其指向第一个结点的后继结点。

    图5-12 升级表尾结点

  • 修改表头指针的值,使其指向其后继结点,移除临时结点。

    图5-13 升级表头并移除临时结点

  • 代码实现:

public void DeleteFrontNodeFromCLL(CLLNode headNode){        //临时结点        CLLNode temp=headNode;        //表尾结点        CLLNode currentNode=headNode;        if(headNode==null){            System.out.print("List Empty");            return;        }        while (currentNode.getNext()!=headNode){            currentNode=currentNode.getNext();        }        //升级表尾结点        currentNode.setNext(headNode.getNext());        //升级表头        headNode=headNode.getNext();        //移除临时结点        temp=null;        return;    }

6、松散链表

与数组相比,链表的最大优势在于,在任何位置插入元素的时间开销仅为O(1)。然而在链表中查找某元素的时间开销则是O(n)。下面详情单向链表的简单变种,称为松散链表。
松散链表中的每个结点存储多个元素(简称为块)。而每一块中的所有结点由循环链表链接在一起。

图6-1 松散链表

  • 假设在任何时候松散链表的元素个数不超过n,为了进一步简化问题,假设除了最后一块外,其它块刚好有? √n?(表示不小于根号n的最小整数),所以在任何时候,松散链表中的个数不会超过?√n?(表示不大于根号n的最大整数)。举个例子,n为10的时候,? √n?=4,?√n?=2。

6.1、在松散链表查找一个元素

在松散链表中查找第k个元素,时间复杂度为O(√n)。具体形容如下:

  • 遍历链表找到包含第k个结点的块,已知每块? √n?个结点,所以在第? k/? √n??块。举个例子,n为10的时候,? √n?=4,假设此时k=9。那么? 9/4?=3,即不小于9/4的最小整数。由于k<=n,所以最多遍历√n个块,那么时间复杂度也就是O(√n)。
  • 接着在这个块的循环链表找到第(k mod ? √n?)个结点。这个过程的时间复杂度同样也是O(√n),起因是每块中的结点个数最多为? √n?。

6.2、在松散链表中插入一个元素

当插入结点的时候,可可以需要调整松散链表中的结点以保证前面提到的链表属性,也就是除了最后一块外,其它块刚好有? √n?个结点。举个例子,如下图:

图6-2 插入元素22

6.3、在松散链表中执行移动操作

上述插入过程中会对少量元素进行移动,使其满足松散链表的相关性质。其实每次移动操作包括从块中的循环链表的表尾移除一个结点,并在下一块中的循环链表的表头插入一个结点,时间复杂度为O(1)。那么能推出在松散链表中插入一个元素的时间复杂度为O(√n),由于最多执行√n次移动操作。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 数据结构——链表

发表回复