数据结构链表结构体定义

So here we are, in the previous post, we learnt array and how it is stored in memory under the hood. However, we also have looked into its drawbacks too. Then what substitute data structure for array? The one of the answer is Linked List.

因此，在上一篇文章中，我们在这里学习了数组以及如何将其存储在后台的内存中。 但是，我们也已经研究了它的缺点。 那用什么替代数组的数据结构呢？ 答案之一是“ 链表” 。

什么是链表？ (What is Linked List?)

Linked List is a data structure works like scattered boxes from here and there rather than sequent lengthy boxes, and each box contains data and an address for the next box. Generally, it is implemented in a class (under the assumption of you knowing object-oriented programming). Imagine the boxes are like post box and there is a letter(actually content, data) and address for the next box, you will have to open the box to get a letter and address. There are three linked list, singly linked list, doubly linked list and circle linked list. I will cover about singly linked list in this post.

链表是一种数据结构，就像从零散到四处散布的盒子 ，而不是随后的冗长的盒子，每个盒子都包含数据和下一个盒子的地址 。 通常，它是在一个类中实现的(假设您知道面向对象的编程)。 想象一下，这些盒子就像邮政信箱，并且下一个盒子有一个字母(实际上是内容，数据)和地址，您将不得不打开盒子来获得一个字母和地址。 共有三个链表，单链表，双链表和圆形链表。 我将在这篇文章中介绍单链列表 。

数组和链接列表之间的区别 (Difference between Array and Linked List)

There are few differences between array and linked list.

数组和链表之间几乎没有区别。

In an array, you have obvious address for the next element that is index. In a linked list, however, it is little uncertain as the boxes are not placed in a sequent order. That means you can access from Nth of element by stating its index number such as arr[7], but to get an access to a data in linked list, you should get a first element(we call it head in linked list) first, then check the next box, and the next of next until you get the data you wanted.

在数组中，下一个元素(索引)的地址很明显。 但是，在链接列表中，不确定性是不确定的，因为这些框未按顺序放置。 这意味着您可以通过声明元素的索引号(例如arr [7] )来从元素的第N个元素进行访问，但是要获得对链表中数据的访问权，您应该首先获取第一个元素(在链表中称为头 )，然后选中下一个框和下一个，直到获得所需的数据。

链接列表的好处 (Benefit of Linked List)

Linked List allows us flexibility in memory allocation, as it does not require you long empty spaces to store datas in memory. Also, if you want to add new element in array that is out of index range, array needs to recreate bigger array to contain all of it. In a linked list, you can simply add additional element with a reference of next element.

链接列表使我们可以灵活地分配内存 ，因为它不需要较长的空白空间即可将数据存储在内存中。 另外，如果要在数组中添加超出索引范围的新元素，则数组需要重新创建更大的数组以包含所有元素。 在链接列表中，您可以简单地添加其他元素以及下一个元素的引用。

Example of memory allocation of linked list 链表的内存分配示例

链表的缺点 (Drawbacks of Linked List)

There are two drawbacks of linked list, as far as I see. One, there is only one entry point called head Let’s say you want to get data from third box, what would you do first to check what is in the third box? The answer is to open a first box to get next box! You then will need to check second box to get an address to third box and now you see there is data 3 in third box. Two, each box requires extra memory spaces for a pointer, which is an address for next box.

据我所知，链表有两个缺点。 一， 只有一个称为head的入口点。假设您要从第三个方框中获取数据，那么您将首先检查第三个方框中的内容吗？ 答案是打开第一个盒子以获得下一个盒子！ 然后，您将需要选中第二个框以将地址获取到第三个框，现在您看到第三个框中有数据3。 二，每个框都需要一个指针 额外的存储空间 ，这是下一个框的地址。

代码示例 (Code Example)

Let’s convey the visual idea to lines of code.

让我们将视觉思想传达给代码行。

Linked list that will contain our nodes will be implemented as following, head represents first element in a linked list and null(or None) by default. However, we are NOT using this list for the simplicity for now.

包含我们节点的链表将按以下方式实现， head表示链表中的第一个元素，默认情况下为null(或None)。 但是，为简便起见，我们暂时不使用此列表。

class LinkedList: def __init__(self): self.head = None

We will implement post boxes, conventionally called node, that contains two properties, data and reference to next node (a.k.a pointer) as following.

我们将实现邮政信箱 ，通常称为node ，其中包含两个属性， 数据和对下一个节点的引用 (即指针) 如下。

class Node: def __init__(self, data): self.data = data self.next = None# Create nodes(post boxes)nodeOne = new Node(1)nodeTwo = new Node(2)nodeThree = new Node(3)# Link them with a pointernodeOne.next = nodeTwonodeTwo.next = nodeThree

When Node is constructed, it will take data integer number for simplicity here, and next node will be set to null(None in python) by default. We then point to next node for each node.

构造Node时，为简单起见，它将采用数据整数，默认情况下，下一个节点将设置为null (在python中为None )。 然后，我们指向每个节点的下一个节点。

node_one -> node_two -> node_three

node_one-> node_two-> node_three

Result of the code above 上面代码的结果

遍历链接列表 (Looping through Linked List)

To loop through an array, we will use for loop like this in Java:

要遍历数组，我们将在Java中使用for循环：

for(int i=0; i < arr.length; i++){ System.out.println(i);}

Picking up from where we left off in our code above. Firstly, we need create empty linked list, then add our node to the list, in this case, our head is nodeOne. Secondly, assign the head a list to a variable current, which will be reference that points to current node. Lastly, we are going to loop the list until there is no next node, meaning node is null/None, so how it works is, you just change current pointer to next one.

从上面的代码中停下来的地方接起。 首先，我们需要创建一个空的链表，然后将我们的节点添加到列表中，在这种情况下，我们的头是nodeOne 。 其次，为head分配一个变量current的列表，它将作为指向当前节点的参考。 最后，我们将循环列表， 直到没有下一个节点，这意味着node为null / None ，所以它的工作方式是，只需将当前指针更改为下一个。

llist = LinkedList()# Add our nodes - nodeOne is a head as it is first element llist.append(nodeOne) llist.append(nodeTwo)llist.append(nodeThree)current = llist.headwhile current.next: print(current) current = current.next

链表方法 (Linked List Methods)

In data structure, there seems like always methods to add and delete datas. There must be methods as well, but I will cover about very commonly used ones.

在数据结构，似乎像往常一样的方法来添加和删除 DATAS。 也必须有方法，但是我将介绍非常常用的方法。

附加() (append())

Time complexity: O(N)

时间复杂度：O(N)

append() is a method that adds data to end of a linked list and its time complexity is O(N), since it needs to traverse all the way to the last.

append()是一种将数据添加到链表末尾的方法，其时间复杂度为O(N) ，因为它需要一直遍历到最后一个。

class LinkedList: def __init__(self): self.head = None def push(self, data): new_node = Node(data) if self.head is None: self.head = new_node return current = self.head while current_node.next: current = current.next current.next = new_node

Code breakdown

代码细目

Create new node using node constructor that contains slots for data and next node reference.

使用包含数据插槽和下一个节点引用的节点构造器创建新节点。 Check whether there is head or not, no head means empty list so the new_node becomes head in this case.

检查是否有头，没有头意味着空列表，因此在这种情况下new_node成为头。 Otherwise, we need to loop through our lists to the end, as we always need to start from head node in the list.

否则，我们需要遍历列表到最后，因为我们总是需要从列表的头节点开始。 Let last node in a list points new_node.

让列表中的最后一个节点指向new_node。

删除(键) (delete(key))

Time complexity: O(N)

时间复杂度：O(N)

There are two ways of deleting datas, I would show you how to delete exact data that I want to delete. In this case, we will delete 2 from our linked list, then we simply need to loop a list until we found the same key from the list. it work almost the same as in looping linked list, except one thing, reference for previous, since there is no way to get a previous reference, we will contain it in a variable temporarily.

删除数据有两种方法，我将向您展示如何删除要删除的确切数据。 在这种情况下， 我们将从链接列表中删除2 ，然后只需要循环一个列表，直到从列表中找到相同的键即可。 它的工作原理几乎与循环链接列表中的工作原理相同，除了一件事，即对previous的引用，由于无法获取先前的引用，我们将其暂时包含在变量中。

Before looping, we need to check whether first element is the key we are after, if so, we can just change head to next element and stop the method. In this case, time complexity is constant time — O(1)

在循环之前，我们需要检查第一个元素是否是我们之后的键 ，如果是，我们可以将head更改为下一个元素并停止该方法。 在这种情况下，时间复杂度是恒定时间-O(1)

if current is not None and current.data == key: self.head = current.next return

Let’s get our references ready:

让我们准备好参考资料：

# in LinkedList classdef delete(self, key):previous = Nonecurrent = self.head

Then create a loop that stops when there is a matching data (key), and each variable becomes its next node.

然后创建一个循环，当有匹配的数据(键)时该循环停止，每个变量成为其下一个节点。

# Loop as long as there is current node and until data is matching.while current is not None and current.data != key: previous = current current = current.next

So now we are here:

所以现在我们在这里：

To know the reason why the loop stopped it would be either of current being null or key being found. If it was current being null, then stop the method by returning.

要知道循环停止的原因，可能是当前为null或找到了键。 如果当前为null，则通过返回停止该方法。

if current is None: return

Otherwise, continue the process, which is pointing from next of previous to next node of current like so:

否则，继续执行此过程，即从上一个节点的下一个指向当前节点的下一个，如下所示：

This is equivalent to :

这等效于：

previous.next = current.next

There are more methods you can add though, I hope you found this article is helpful for grasping the concept. Cheers!

不过，您可以添加更多方法，希望您发现本文对理解该概念有所帮助。 干杯!

翻译自: https://medium.com/swlh/learning-data-structure-02-linked-list-efac931863c8

数据结构链表结构体定义

相关资源：四史答题软件安装包exe