二叉树之下程序员Android-技术

数据结构——链表

2018-06-25  本文已影响118人  我哈啊哈啊哈

目录

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、数组和链表优缺点

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、链表的遍历

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

下面是遍历函数的声明：

    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指针），如下步骤：

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

若要在表尾后插入一个新结点，则需要修改两个next指针（最后一个结点的next指针和新结点的next指针），如下步骤：

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

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

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.1.3.2、删除链表的表尾

该操作比删除链表的第一个结点要稍微复杂一些，因为算法需要找到表尾结点的前驱结点。分三步实现：

3.1.3.3、删除链表中间的结点

这种情况下，被删除的结点总是位于两个结点之间，因此不需要更新表头和表尾的指针。分两步实现：

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、在双向链表的开头插入结点
4.1.2、在双向链表的末尾插入结点

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

4.1.3、在双向链表的中间插入一个结点
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.2.2、删除双向链表的最后一个结点

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

4.2.3、删除双向链表中间的一个结点
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、在循环链表的表尾插入结点

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

 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、在循环链表的表头插入结点

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

 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指针指向第一个结点。

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指针指向第一个结点的后继结点。

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 松散链表

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

在松散链表中查找第k个元素，时间复杂度为O(√n)。具体描述如下：

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

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


图6-2 插入元素22

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

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

上一篇 下一篇

猜你喜欢

热点阅读