Hey, guys. I’m balls.

As mentioned in the Array article, contiguous memory makes arrays move a lot of elements when inserting and deleting, which means time consuming.

When it comes to data structures and algorithms, fast man is the favorite, and persistent blue kids like insert and delete are obviously not appreciated.

Later, people tried to help them get faster.

Is there a data structure that can do this?

The linked list was made.

Linked lists are slightly more complex data structures than arrays, but they are not difficult to learn by following the script.

The list

First of all, what is a linked list?

The linked storage structure of a linear list generates a list called a linked list.

So what is chained storage?

The chained storage structure refers to the use of a set of arbitrary storage cells to store the data elements of a linear table, connected in series by pointer connections.

By “arbitrary” I mean that storage units can be contiguous or discontiguous, which means they can be anywhere in memory that is not occupied. Smell point is to say that as long as the memory of this toilet empty latrine, you squat casually.

The storage units in a linked list are called nodes. Instead of an array containing only data information, each node is divided into two parts: a data field and a pointer field. A data field stores data. A pointer field stores the location of the next node in the same table.

Because there are too many brothers and sisters in the linked list family, I will only talk about the common types of linked list structures: singly and bidirectionally linked lists.

After all, any more writing would kill me.

Singly linked lists

N nodes can be linked to form a linked list. If each node in a linked list contains only one pointer field, the list is called a singly linked list.

The pointer field of a singly linked list points to the address of the next node. We call the pointer to the address of the next node a successor pointer.

The location of the first node in a singly linked list is called the head pointer, and the subsequent pointer to the last node is NULL, usually represented by NULL or ^.

In addition to the above, sometimes for ease of operation, a single linked list is preceded by a node, called the head node. This header node typically stores nothing, and its pointer field points to the first node in a single list.

Stinky: Stop, stop, stop! Both a header pointer and a header node… Balls: Don’t panic, I got you.

The difference between a header pointer and a header node

A header pointer, as the name implies, is a pointer to the first node in the list, or to the first node, if any.

* * it is a list of essential element and whether the list is empty, the head pointer is not empty, because when they visit the list you have to know in what position, so as to find the next node through the pointer field position, that is to say, know the head pointer, the entire list of elements we are accessible.

So you have to have a header pointer, and that’s what we call an identifier, and that’s why we use a header pointer to represent a linked list.

The head node, which precedes the node of the first element, is generally meaningless in its data field, and is itself not required in the list.

It is set up purely for the unity and convenience of operation, in fact, in order to make it more convenient to operate the linked list at some time. With the head node, when we insert or delete the node before the first element, its operation is unified with the operation of other nodes.

In addition, there is a kind of nothing, nothing.

I don’t know if you noticed this, but no matter whether the list is empty or not, they all have a header pointer. This confirms what I mentioned above: “The header pointer is an essential element of the list. No matter whether the list is empty or not, the header pointer can not be empty”.

Don’t talk, praise me ~

Operation of a single linked list

Like arrays, singly linked lists have operations like find, insert, and delete. Because the storage space of linked lists is discontinuous, the insertion and deletion operations of linked lists are fast.

The insert

Suppose we want to do an insert: insert node S after node P.

To do this, simply insert s between p and p. ext.

As you can see from the above figure, the insertion of a singly linked list does not need to alert other nodes at all. It only needs to change the Pointers of s.ext and P.ext. Let s’s successor point to p’s successor, and then P’s successor point to S, and remember that the order of the insertions must not be changed.

You can see that the time complexity of the insert operation is O(1).

Delete operation

Suppose we want to perform a delete operation: remove the successor node Q of node P.

In fact, it is also simple, that is, the successor pointer of P can bypass Q and point directly to the successor node of Q. Specific operations are shown in the following figure.

As can be seen from the figure above, it only takes one step to implement the deletion operation, that is, direct p.ext to q.ext, so the time complexity of the deletion operation is O(1).

Find operations

Of course, where there is fast there is slow, element lookup is the fly in the ointment of linked lists.

Array rows are different in memory. The addresses of the linked list are scattered in memory, and the location of the current node can only be known through the next of the previous node. Therefore, if you want to find the ith element in the linked list, you have to start from the beginning until you find the ith element.

From this we can see that the time complexity of the lookup operation in the linked list is O(n).

Single – linked list application scenarios

Single linked list said so much also almost, hot yao have a question, I learned this thing can be used in where?

Easy!

The application of single linked list can be used in two scenarios:

(1) The first basic operation. You don’t want to waste too much time on insert and delete operations in your application scenario. Using a single linked list can improve insert and delete time.

(2) The second kind of coquettish. In the scenario where you’re applying, and you don’t know how many elements there are, you’re using a single linked list, and every time you get a new element you’re chained to the list, that’s a great way to do it with a linked list. And it’s easy to overlook.

Two-way linked list

Bidirectional lists, as the name suggests, are linked lists in two directions. Compared to a single linked list, it has a precursor pointer, prev, to the precursor node. So the bidirectional list can go either backwards or forwards.

As can be seen from the above two figures, bidirectional linked lists have one more precursor pointer, which takes up more space in memory than single linked lists. However, bidirectional linked lists are more convenient for querying linked list elements. For example, they can find the precursor node of the current node in O(1) time, which is a typical space for time.

Space for time: In the case of sufficient memory, data structures or algorithms with high space complexity and low time complexity are selected to pursue faster execution speed.

Now that we’ve swapped time for space, where are bidirectional lists faster than single lists? So let’s start with insert and delete.

You might pick up the keyboard here and say, well, single list inserts and deletes are already O(1), how fast can we do that?

In fact, to be precise, insert and delete are O(1), more for the single action of insert or delete, in reality, everything has preconditions. In some scenarios, bidirectional lists are faster than single lists.

Let’s start the show.

Advantages of insertion operation

There are two types of insert operations:

  • Insert a new node before or after the node whose data field is equal to a specific value.

  • Inserts a new node before or after the given node.

For the first, the time complexity of the two is similar. It’s all in two steps:

The first step is to find the nodes whose data field is equal to a specific value. Both single and bidirectional lists need to be traversed from the beginning one by one. The time complexity of this step is O(n).

The second step is insertion. If is inserted into the back, the time complexity is O (1), if is inserted, the singly linked lists slower, it needs to find the precursors of specific value node, the time and cost of O (n), and two-way chain table need not, because it has the precursor nodes, nodes directly can find the specific value of precursor, This time is order 1.

In case 2, which is actually step 2 in case 1, we’ve already found the node we want to insert, and if we’re both inserting backwards, the time of single and double linked lists is the same, order 1. The difference is the forward insertion, which requires knowing the precursor node of the current node. Single-linked lists need to iterate to the precursor node of the current node, and the total time complexity is O(n), while bidirectional lists can find its precursor node in a short time, and the time complexity is O(1).

This is where bidirectional lists have an advantage over single lists.

Advantages of deleting operations

Delete operations, similar to insert operations, are basically two cases:

  • Delete the node whose data field is equal to a specific value.

  • Deletes the given node.

The first case is not mentioned, singly linked list and bidirectionally linked list are the same, they are all traversed from scratch, time is O(n).

In the second case, deleting a given node requires knowing the precursor node of the node. The single linked list needs to be searched from the beginning until “node.next = current node” is appropriate to find the precursor node of the current node. The time complexity of this process is O(n). A bidirectional list, on the other hand, knows its precursor directly, and it only takes O(1) to do it.

Common linked lists to this finished, of course, derived on this basis like circular linked lists, circular bidirectional linked lists are not said, a whole too much afraid of your indigestion.

I will brush in the later part of the problem slowly give you all understand, to ensure that the smelly treasure service clearly ~

Two good sources are recommended here, one is a note and the other is an optimal solution, the two together are invincible. Score 70K star in two months, leetcode optimal solution of students with outstanding academic performance in Tsinghua

Linked list this thing, don’t be afraid, although it looks a little complicated, but in fact it is just a few plate axe, when learning linked list draw more on paper, there is no hiding from all kinds of relations, what is the whole understand, do not believe you try.

Of course, can see this is true love, one key three connect message yao yao da to me brush up ~

I’m balls. I’ll see you next time!