文章目录
程序 = 数据结构 + 算法
- 数据结构是程序的骨架
- 算法是程序的灵魂
其实各种数据结构的要点–无外乎：定义 + 操作。
这一次，从Go语言开始，彻底学懂数据结构与算法，Let’s Go~~~
一、数组 / 顺序表
1. 静态分配
用一个定长数组data[]存储数据，最大空间为Maxsize，用length记录实际的元素个数，即数组的长度。
2. 动态分配
采用动态存储方法，在运算过程中，如果发生溢出，可以另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的。
3.操作
访问：O(1)
插入:平均O(n)
删除:平均O(n)
二、链表
LinkedList 链表，是一系列节点，这些节点会引用该序列的下一个节点。
它也是一种线性数据结构，也用于存储数据。可以很方便的在某个任意节点处进行添加和删除某个节点的操作。
链表在内存中不是连续存储的。
1.单链表
节点定义
Node 节点类，具有某类属性的变量，比如可以是整型、浮点型…该类同时还有一个名为nextNode的变量，它是一个指针类型。这里以最简单的整型列表为例，如下所示：
// Node class type Node struct { Var int nextNode *Node }
单链表定义
一环接一环。
- 改善数组插入和删除操作的繁琐
- 在不知道有多少元素，使用单链表，可以减少内存
// Definition for singly-linked list. type LinkedList struct { headNode *Node }
操作
需要熟练掌握的操作如下：
- 遍历整个链表：
O(n) - 访问某个元素：
O(n) - 插入节点:
O(1) - 删除节点:
O(1)
2. 双链表
定义
既有前驱，又有后继节点。
这意味着每个节点都连接到两个节点，我们可以向前遍历到下一个节点，也可以向后遍历到上一个节点。
// Node class type Node struct { Var int nextNode *Node previousNode *Node }
操作
双链表允许插入、删除和遍历操作。
3. 循环链表
循环链表是一种特殊的单链表。
循环链表跟单链表唯一的区别就在尾结点。单向链表的尾结点指针指向空地址，表示这就是最后的结点了，而循环链表的尾结点指针是指向链表的头结点，它像一个环一样首尾相连，所以叫作“循环”链表。
题目练习
Leetcode 题解
Go代码：
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseList(head *ListNode) *ListNode { if head == nil { return nil } var pre *ListNode for head == nil { tmp := head.Next head.Next = pre pre = head head = tmp } return pre }
Java代码：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; // 当前节点的前一个位置 ListNode cur = head; // 当前节点 ListNode tmp = null; // 当前节点的后一个位置 while(cur != null) { // 因为cur.next只能指向一个方向，现在需要指向前面 // 1.记录当前节点的后一个位置， tmp = cur.next; // 2. 当前节点指向pre，调转方向 cur.next = pre; // 3. pre和cur都向前进一步 pre = cur; cur = tmp; } return pre; } }
