专栏首页SAMshare[013] 7种常见数据结构的图画解读

[013] 7种常见数据结构的图画解读

“数据结构在我们做数据过程中会经常遇到的,算法的实现更是依赖。今天给大家分享的这篇文章,对我们工作中最为常用的数据结构进行了结构化解释,同时也有一些图画,更加容易理解,希望可以帮助到大家哦!

Data structures are fundamental constructs that are used to build programs. Each data structure has its own way of organizing data, which may work efficiently in particular use cases. With their own particular structures, data structures offer alternative solutions to data organization, management, storage, access, and modification tasks.

Regardless you are building a machine learning model or a mobile app; you must rely on data structures when working on a project. Therefore, your prospective employer will also want to make sure that you have a good grasp of data structures.

In this post, we will cover seven fundamental data structures that you must know for your next job interview.

1. Arrays

Arrays are the most simple and widely used data structures. They are constructed as a collection of elements in a specific order. Arrays usually have fixed-size, and they hold items of the same data type. You can create an array from the collection of strings, integers, objects, or even arrays. Since arrays are indexed, you can have random access to any array element.

Figure 2. An Example Visualization of Arrays (Figure by Author)

Types of Arrays: The two most common types of arrays you may come across to are

  • One-dimensional arrays
  • Multi-dimensional arrays

Basic Operations on Arrays: The most common basic operations you can conduct on arrays are insert, get, delete, and size operations.

  • Insert: Inserting a new element at a given index
  • Get: Returning an element at a given index
  • Delete: Deleting an element at a given index
  • Size: Returning the total number of elements in an array

You can also conduct traverse, search, and update operations on arrays.

Implementation of Arrays:

  • Arrays are usually used as building blocks of more complex data structures such as arrays, lists, heaps, matrices.
  • In data science, arrays are used for efficient data manipulation operations. We often provide NumPy’s array objects to machine learning models for training.

2. Stacks

Stacks are data structures that work on a LIFO (Last in First Out) basis. In a LIFO based data structure, the data that are placed the last is accessed first. A real-life example of a stack could be a pile of rocks placed in vertical order, as shown in Figure 2.

Figure 3. Photo by Samrat Khadka on Unsplash

Basic Operations on Stacks: The most common basic operations you can conduct on stacks are push, top, pop, isEmpty, and isFull operations.

  • Push: Inserting a new element to the top;
  • Top: Returning an element at the top without removing it from the stack;
  • Pop: Returning an element at the top after removing it from the stack; and
  • isEmpty: Checking if the stack has any element.
  • isFull: Checking if the stack is full.

Here is a visualization of stack structure:

Figure 4. An Example Visualization of Stacks (Figure by Author)

Commonly asked interview questions regarding stacks

  • Evaluating postfix expression using a stack (e.g., Reverse Polish notation (RPN), or an abstract syntax tree (AST));
  • Sorting values in a stack; and
  • Checking balanced parentheses in an expression.

3. Queues

Queues are structurally very similar to stacks. The only difference is that queues are based on the FIFO (First In First Out) method. In a queue, we can either add a new element to the end or remove an element from the front. A real-life example of queues could be a line of people waiting in a grocery, as shown in Figure 4.

Figure 5. Photo by Adrien Delforge on Unsplash

Basic Operations on Queue: The most common basic operations you can conduct on queues are enqueue, dequeue, top, and isEmpty operations.

  • Enqueue: Inserting a new element to the end of the queue;
  • Dequeue: Removing the element from the front of the queue;
  • Top: Returning the first element of the queue; and
  • isEmpty: Checking if the queue is empty.

Here is a visualization of queue structure:

Figure 6. An Example Visualization of Queue (Figure by Author)

Implementation of Queues and Common Interview Questions

  • Implement a queue using stacks;
  • Retrieve the first n elements of a given queue; and
  • Generate binary numbers from 1 to n.

4. Linked Lists

Linked lists are structured as a linear collection of elements (i.e., node). Each node contains two information:

  • Data: The value of the element
  • Pointer: The pointer to the next node in the linked list.

Since linked lists are sequential structures, accessing elements randomly is not possible.

Figure 7. Photo by JJ Ying on Unsplash

Types of Linked List: We come across two main types of linked lists,

  • Singly Linked List: We can only access the next node using the node before it.
  • Doubly Linked List: We can access data both in forward and backward directions.

Here is a visualization of a linked list structure:

Figure 8. An Example Visualization of Single Linked List (Figure by Author)

Basic operations of Linked List: The most common basic operations you can conduct on linked lists are insertAtEnd, insertAtHead, DeleteAtHead, Delete, and isEmpty operations.

  • InsertAtEnd: Inserting a new element to the end of the linked list
  • InsertAtHead: Inserting a new element to the head of the linked list
  • DeleteAtHead: Removing the first element of the linked list
  • Delete: Removing a given element from the linked list
  • isEmpty: Checking if the linked list is empty.

Commonly asked Linked List interview questions:

  • Find the middle element of a singly linked list in one pass;
  • Reverse a singly linked list without recursion; and
  • Remove duplicate nodes in an unsorted linked list.

5. Trees

Trees are hierarchical data structures that consist of nodes and edges. Nodes represent values while edges connect them. The relationship between nodes in a tree is a uni or bidirectional one, not a cyclical one. Trees are widely used to build decision trees and ensemble methods.

Figure 9. Photo by Jazmin Quaynor on Unsplash

While tree types like binary trees and binary search trees are the most commonly used variations, the total number of different tree implementations reaches hundreds, where they can be grouped as:

  • Basic Tree Structures
  • Multi-Way Trees
  • Space-Partitioning trees
  • Application-Specific trees

Figure 10. An Example Visualization of Single Linked List (Figure by Author)

Commonly asked Tree interview questions:

  • Check if two given binary trees are identical or not;
  • Calculate the height of a binary tree;
  • Construct a full binary tree from a preorder and postorder sequence.

6. Graphs

Graphs consist of a finite set of nodes (i.e., vertices) with a set of unordered or ordered pairs of these vertices that together form a network. These pairs are also referred to as edges (i.e., links, lines, or arrows). An edge may contain weight or cost information to represent how much it cost to move from a to b.

Figure 11. An Example Visualization of Graph (Figure by Author)

Types of Graphs: There are two main types of graphs: (i) directed graphs and (ii) undirected graphs.

  • Directed Graphs: If all the edges of a graph have direction info like in Figure 8, then we talk about a directed graph;
  • Undirected Graphs: If none of the edges have direction info, then we talk about an undirected graph

Figure 12. Directed Graph vs. Undirected Graph (Figure by Author)

Basic operations of Graphs: The most common basic operations you can conduct on graphs are adjacent, neighbors, add_vertex, remove_vertex, add_edge, remove_edge, and get operations.

  • adjacent: checks if there is an edge from the vertex a to the vertex b;
  • neighbors: lists all vertices b such that there is an edge from the vertex a to the vertex b;
  • add_vertex: adds the vertex a;
  • remove_vertex: removes the vertex a;
  • add_edge: adds the edge from the vertex a to the vertex b;
  • remove_edge: removes the edge from the vertex a to the vertex b,
  • get: returns the value associated with the vertex a or edges.

Commonly asked Graph interview questions:

  • Find the path between given vertices in a directed graph;
  • Check if the given Graph is strongly connected or not; and
  • Check if an undirected graph contains a cycle or not.

7. Hash Tables

Hash tables are associative data structures that store data in an array format with a unique index value. In hash tables, accessing random elements are very efficient and fast as long as we know the index value. Besides, data insertion, deletion, and search are also very fast in hash tables regardless of size. Hash tables use a hashing function to generate efficient index values, which gives them a further advantage of efficiency.

Hashing

Hashing is a method to convert key values into a range of indices of an array. The reason for hashing is to reduce the complexity of key pairs and create an efficient indices list.

Figure 13. An Example Visualization of Hash Table (Figure by Author)

The performance of hashing data structure depends on (i) Hash Function, (ii) Size of the Hash Table, and (iii) Collision Handling Method. One of the combined methods used for hashing and collision handling is combining the modulo operator with linear probing so that the complexity can be reduced to a greater extent while ensuring unique index values.

Commonly asked Hashing interview questions:

  • Find symmetric pairs in an array;
  • Trace the complete path of a journey;
  • Find if an array is a subset of another array; and
  • Check if given arrays are disjoint.

本文分享自微信公众号 - SAMshare(gh_8528ce7b7e80),作者:Orhan G. Yalçın

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-01-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 多图,一文了解 8 种常见的数据结构

    前几天和丙弟交流,他说我们写作的人都是在不停地燃烧自己,所以需要不停地补充燃料。对于他的观点,我不能再苟同了——所以我开始狂补计算机方面的基础知识,这其中就包括...

    沉默王二
  • 【算法】图文并茂,一文了解 8 种常见的数据结构

    百度百科对数据结构的定义是:相互之间存在一种或多种特定关系的数据元素的集合。定义很抽象,需要大声地朗读几遍,才有点感觉。怎么让这种感觉来得更强烈,更亲切一些呢?...

    黄博的机器学习圈子
  • 图解!24张图彻底弄懂九大常见数据结构!

    数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊...

    cxuan
  • 零基础学编程025:前24课总结

    学会如何学习 2016年12月21日,写下了“零基础学编程”的首篇文章:“零基础学编程”都需要哪些基础?计算机都是从0开始计数,所以就叫第0篇文章了。学习任何技...

    申龙斌
  • pygame-KidsCanCode系列jumpy-part8-记录历史最高分

    通常在多玩家的游戏中,每个玩家都会有自己的得分,最高分数会成为该游戏的最佳记录。这一篇,学习下如何记录最高得分:(为了简化代码,本文采用文件方式,仅记录本机得分...

    菩提树下的杨过
  • 集群JournalNode服务重启导致NameNode挂掉分析

    在我们的集群中修改了JournalNode服务的配置后需要重启时配置生效,在进行重启操作时导致NameNode服务挂掉,具体操作步骤如下:

    Fayson
  • 一文读懂 Redis 常见对象类型的底层数据结构

    Redis 是一个基于内存中的数据结构存储系统,可以用作数据库、缓存和消息中间件。Redis 支持五种常见对象类型:字符串(String)、哈希(Hash)、列...

    肉眼品世界
  • 解读 | 数据科学领域常见的3种职业转型方向

    在大学我学习物理时,每当遇到不理解的术语,我就会上网搜索,这时我常会用到的就是维基百科。

    CDA数据分析师
  • 浅析Numpy.genfromtxt及File I/O讲解

    Python 并没有提供数组功能,虽然列表 (list) 可以完成基本的数组功能,但它并不是真正的数组,而且在数据量较大时,使用列表的速度就会慢的让人难受。为此...

    Angel_Kitty
  • 图解:数据结构中的6种「树」,大鹏问你心中有数吗?

    数据结构这门课程是计算机相关专业的基础课,数据结构指的是数据在计算机中的存储、组织方式。

    灵魂画师牧码
  • 以股票RSI指标为例,学习Python发送邮件功能(含RSI指标确定卖点策略)

    本人之前写过若干“给程序员加财商”的系列文,目的是通过股票案例讲述Python知识点,让大家在学习Python的同时还能掌握相关的股票知识,所谓一举两得...

    用户1153489
  • [C#6] 5-自动属性增强

    0. 目录 C#6 新增特性目录 1. 老版本代码 1 internal class Person 2 { 3 public string Nam...

    blackheart
  • 【图解数据结构】一组动画彻底理解堆排序

    由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

    五分钟学算法
  • 重温数据结构:二叉树的常见方法及三种遍历方式 Java 实现

    树的分类有很多种,但基本都是 二叉树 的衍生,今天来学习下二叉树。 ? 什么是二叉树 Binary Tree 先来个定义: 二叉树是有限个节点的集合,这个集合...

    张拭心 shixinzhang
  • 经典卷积神经网络(CNN)结构可视化工具

    本文将介绍一种在线网络工具,可用于可视化各种经典的卷积神经网络结构。学习Caffe的同学,一定很熟悉Netscope。它就是用来可视化Caffe的prototx...

    Amusi
  • 【图解数据结构】 一组动画彻底理解桶排序

    由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

    五分钟学算法
  • 大咖说数据分析的方法

    数据可视化就是把枯燥的数据用图形化的方式展示出来,从而能够更好地理解数据背后的含义。数据可视化有广义和狭义两种理解,狭义的理解就是将数据用图表的形式表达出来,广...

    明悦数据
  • 多点生活面试官:说说常见的几种索引数据结构,他们的优缺点!

    在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页...

    Java程序猿
  • 【图解数据结构】 一组动画彻底理解计数排序

    由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券