算法入门很简单:数组和链表

举报
宇宙之一粟 发表于 2022/06/30 23:39:39 2022/06/30
【摘要】 一、数组 / 顺序表 1. 静态分配 2. 动态分配 3.操作 二、链表 1.单链表 节点定义 单链表定义 操作 2. 双链表 定义 操作 3. 循环链表 题目练习我们都知道:程序 = 数据结构 + 算法数据结构是程序的骨架算法是程序的灵魂其实各种数据结构的要点–无外乎:定义 + 操作。 一、数组 / 顺序表 1. 静态分配用一个定长数组data[]存储数据,最大空间为Maxsize,用l...

我们都知道:

程序 = 数据结构 + 算法

  • 数据结构是程序的骨架
  • 算法是程序的灵魂

其实各种数据结构的要点–无外乎:定义 + 操作

一、数组 / 顺序表

1. 静态分配

用一个定长数组data[]存储数据,最大空间为Maxsize,用length记录实际的元素个数,即数组的长度。

2. 动态分配

采用动态存储方法,在运算过程中,如果发生溢出,可以另外开辟一块更大的存储空间,用以替换原来的存储空间,从而达到扩充存储空间的目的。

推荐:用最复杂的方式学会数组(Python实现动态数组)

3.操作

访问:O(1)

插入:平均O(n)

删除:平均O(n)

二、链表

LinkedList 链表,是一系列节点,这些节点会引用该序列的下一个节点。

它也是一种线性数据结构,也用于存储数据。可以很方便的在某个任意节点处进行添加删除某个节点的操作。

链表在内存中不是连续存储的。

1.单链表

节点定义

Node 节点类,具有某类属性的变量,比如可以是整型、浮点型…该类同时还有一个名为nextNode的变量,它是一个指针类型。这里以最简单的整型列表为例,如下所示:

// Node class
type Node struct {
  Var int
  nextNode *Node
}

单链表定义

一环接一环。

  1. 改善数组插入和删除操作的繁琐
  2. 在不知道有多少元素,使用单链表,可以减少内存
// 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. 循环链表

循环链表是一种特殊的单链表。

循环链表跟单链表唯一的区别就在尾结点。单向链表的尾结点指针指向空地址,表示这就是最后的结点了,而循环链表的尾结点指针是指向链表的头结点,它像一个环一样首尾相连,所以叫作“循环”链表。

题目练习

  1. 反转链表

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;
    }
}
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。