数据结构1.02--链表

发表于 | 分类于 ， | 本文总阅读量 次
字数统计: 2k | 阅读时长 ≈ 7

数据结构与算法笔记（二）————链表

为何数组都从0开始编号

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。如果用a来表示数组的首地址，a[0]就是偏移为0的位置，也就是首地址，a[k]就表示偏移k个type_size的位置，所以计算a[k]的内存地址只需要用这个公式：a[k]_address = base_address + k * type_size
但是，如果数组从1开始计数，那我们计算数组元素a[k]的内存地址就会变为：a[k]_address = base_address + (k-1)*type_size,对比两个公式不难发现，从1开始编号，每次随机访问数组元素都多了一次减法运算，对于CPU来说，就是多了一次减法指令。

数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从0开始编号，而不是从1开始。
C语言设计者用0开始计数数组下标，之后的Java、JavaScript等高级语言都效仿了C语言，或者说，为了在一定程度上减少C语言程序员学习Java的学习成本，因此继续沿用了从0开始计数的习惯。实际上，很多语言中数组也并不是从0开始计数的，比如Matlab。甚至还有一些语言支持负数下标，比如Python。

单链表

有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最
后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。
我们知道，在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是O(n)。而在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的。
但是，有利就有弊。链表要想随机访问第k个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

循环链表

循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。它像一个环一样首尾相连，所以叫作“循环”链表。
和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。

双向链表

每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内
存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。
从结构上来看，双向链表可以支持O(1)时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简
单、高效。

数组链表性能大比拼

1
2
3
时间复杂度	数组	链表
插入删除	O(n)	O(1)
随机访问	O(1)	O(n)

五种基本的单链表问题

不管是哪一种链表问题，都最好画图来辅助理解。

单链表反转

我学会的单链表反转用的方法是用三个指针，一个指针做prev前驱指针，一个指针指向头指针p，一个指针指向头指针的后继节点。思想就是这三个指针的相对位置不改变，一直从头结点往后移动，每移动一次都要改变它们的next后继节点的值，从而就改变了链表的指向，从而实现了链表的反转。
写的代码如下：

1
2
3
4
5
6
7
8
9
10
11
function ReverseList(pHead)
{
    var pre=null,p=pHead,next;
    while(p!=null){
        next=p.next;
        p.next=pre;
        pre=p;
        p=next;
    }
    return pre;
}

链表中环的检测

这个问题的解决思想在于，用两个指针：快指针和慢指针，同时从头节点开始移动，直到它们重合的哪一个位置就是环的入口。

1
2
3
4
5
6
7
8
9
10
function huan(head){
	var p1=head.next;//慢指针，一次走一步
	var p2=head.next.next;//快指针，一次走两步
	while(p1!=p2){
		p1=p1.next;
		p2=p2.next.next;
	}
	return p1;

}

两个有序的链表合并

两个有序的链表合并思想在于，我用另外一个链表来装合并后的链表，首先从两个链表的头节点开始比较大小，（如果从小到大排序）就将小的值存进新链表，并且原链表结点往后移动一位，再继续比较。

1
2
3
4
5
6
7
8
9
10
11
12
function hebing(pHead1,pHead2){
	var result = {};
    if (pHead1.val < pHead2.val) {
        result = pHead1;
        result.next = Merge(pHead1.next, pHead2);
    } else {
        result = pHead2;
        result.next = Merge(pHead1, pHead2.next);
    }
    return result;

}

删除链表倒数第n个结点

用两个指针之间的距离来表示倒数，直到最后一个指针指到末尾，这个时候的前指针指的就是倒数第你、个结点，倒数第n个结点，也就

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function FindKthToTail(head,k)
{

    var p1=head,p2=head;
    if(k<=0){
        return false；
    }else{
        for(var i=0;i<k-1;i++){
            if(p2.next!==null){
                p2=p2.next;
                
            }else{
                return false；
            }
            
        }
        while(p2.next!==null){
            p1=p1.next;
            p2=p2.next;
        }
        return p1;
    }
}

另一种方法是借用数组来表示

1
2
3
4
5
6
7
8
9
10
function FindKthToTail(head,k)
{
    var arr=[];
    while(head!=null){
        arr.push(head);
        head=head.next;
    }
    var len=arr.length;
    return arr[len-k];
}

求链表的中间结点

这个也有一种巧妙的算法，也是用一个快慢指针来实现的，快指针一次走两步，慢指针一次走一步，那么在快指针走到链表末尾的时候，慢指针走的永远是快指针的一半，只是当链表节点个数是偶数的时候，指向的是中间偏后一个结点。

1
2
3
4
5
6
7
8
function middle(head){
	var p1=head,p2=head;
	while(p2!=null){
		p1=p1.next;
		p2=p2.next;
	}
	return p1;
}

当然还可以用数组的方式来写

1
2
3
4
5
6
7
8
9
function middle(head){
	var arr=[];
	while(head!=null){
		arr.push(head);
		head=head.next;
	}
	var len=arr.length;
	return arr[length/2];
}
-------------本文结束感谢您的阅读-------------