本文共 1713 字，大约阅读时间需要 5 分钟。

所有关于数据结构这一块的知识今天刚接触，如有理解错误，感谢指出！ 在查阅数据结构理解的过程中，同时也第一次在CSDN记录下博客。

关于我所理解的链表

举个例子:

A有一个int数值 又有一个指针指向B B有一个int数值 又有一个指针指向C ... ... 然后就形成了一个单向链表，同时，每个节点里面都储存着一个int数值。 A→B→C→... 同理，如果B不仅保有指向C的指针且有指向A的指针，就形成了一个双向链表。 A↔B↔C↔... 得了了链表的首节点A，即得到了之后后续所有节点的数据。 数据以int类推，每个节点储存的不仅仅只有int，也可以是对象。

ArrayList和LinkedList的效率比较

ArrayList实现是数组，LinkedList的实现是双向循环链表。 也是因为数组除了对最后一个元素，每次插入或删除时，内存地址都需要移动， 而链表不需要，所以ArrayList查询快，LinkedList增删快。 数组的内存地址连续，大小固定，不适合进行动态的存储。 链表只能通过顺序指针进行访问，所以查询的速度慢，而增删速度快。

单向链表、双向链表与循环链表

单链表和双链表的区别就是，双链表不仅保存指向下一个元素的指针，且保留指向上一个元素的指针 循环链表即让最后一个元素保存指向头元素的指针

常用的链表方法

1.求倒数第k个节点

定义两个指针遍历，第一个指针先走k次，第二个指针开始走，

当第一个指针走到了，第二个指针就是倒数第k个节点

2.求中间节点

同上，第一个指针走一步，第二个指针走两步，当第二个指针走到时。

3.判断是否有环

同上，第一个指针走一步，第二个指针走两步，当两个节点相同时。

4.求循环链表中环的长度

按方法3找出循环的节点是什么，循环该节点直至等于自己，即可找出。

5.求两个单链表的第一个交点

算出A链表长度A，B链表长度B，长度相减得出C。

长的链表先走C步，A，B剩余长度相同，同时走，当相同时即得出交点。

总结单链表的反转

第一种方法：

单链表储存为数组，通过数组反转。

第二种方法：

反转指针，首指针指向null。

网上代码大同小异，取关键部分举1,2节点来说明： current为当前节点，此时为1节点，reverseHead为指向节点,此时为null while (current != null) { next = current.next;  //将1节点的下一节点保存      1 current.next = reverseHead; //将1节点指向null      2 reverseHead = current; //将1节点赋值给指向节点     3 current = next;//当前节点后移                     4 } 第一轮：将1节点的下一节点保存，将1节点指向null，将1节点赋值给指向节点，当前节点后移。 第二轮：将2节点的下一节点保存，将2节点指向1节点，将2节点赋值给指向节点，当前节点后移。 容易理解为: 1,4步骤其实就是保存下一节点，将当前节点后移。 2,3步骤是将当前节点指向上一次循环保存的节点，保存当前节点给下一节点。 再容易理解为： 要反转null→1→2的指针，需要先保存1节点为reverseHead,将1节点指向reverseHead=null 后移为2节点，保存2节点为reverseHead，2节点指向reverseHead=1, 后移通过next = current.next; current = next;实现。 1→2→3→4→null 第一轮：null←1→2→3→4→null 第二轮: null←1←2→3→4→null ... ... 然后成功反转链表。

第三种方法：

将2-N节点依次插到第2节点，最后把首节点插到末尾。

即，1,2,3,4,5 第一轮  1,2空3,4,5

第二轮：1指向3,3指向2,   1,3，2空4，5

第三轮：1指向4,4指向3，  1,4,3,2空5

第四轮: 1指向5,5指向4，  1,5,4,3,2

第五轮: 1移至最后   5,4,3,2,1

第四种方法：

递归，这一块还没有去看具体实现。先总结到这里。

转载地址：http://priob.baihongyu.com/