5. Linked list introduction to mind method

❝

Linked lists are slightly more complex data structures than arrays, and are also two very important and basic data structures. If an array is a disciplined, orderly army, linked lists are a flexible underground party.

❞

Follow the public account MageByte for the great stuff you want.

A linked list is a non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by linking the order of Pointers in the linked list. A linked list consists of a series of nodes (each element of the list is called a node) that can be dynamically generated at run time. The nodes of a linked list consist of data and one or more pointer fields. If the search for elements before insert and delete operations is not considered, and pure insert and delete operations are only considered, then the linked list algorithm on insert and delete operations is complex O(1).

Linked list large aggregation

We have seen in the movie, a spy only know their own superior, inferior information, underground party through this single line contact of the way flexible secret transmission of the message. There are also many types of linked list family, the simplest single linked list, circular linked list, two-way linked list, two-way circular linked list.

The biggest difference between the underlying data structure and the array is that “the array needs a contiguous memory space to store, while the linked list does not need a contiguous memory space. It connects a group of scattered memory blocks in series through” Pointers “. This is the essence reason that underground party is flexible and changable, can switch his upper and lower levels at any time.

Singly linked lists

We call the memory block “nodes” of the linked list. In order to connect all the scattered nodes together, each node in addition to storing data, also needs to record the address of the next node of the node, which is called “next pointer”.

There are two nodes to note: the first node “head node” and the last node “tail node”. The head node records the base address of the list, so that the whole list can be traversed, while the “next” of the tail node only wants an empty address, NULL, to indicate that it is the last node.

The deletion and insertion operations of the linked list only need to consider the pointer changes of adjacent nodes, so the time complexity is O(1).

There are pros and cons. If a list wants to randomly access the JTH element, it’s not as efficient as an array. The data of linked list is not stored continuously, so the corresponding memory address of J position can not be calculated by addressing formula according to the initial address and subscript like array. It is necessary to traverse node by node according to pointer until the corresponding node is found.

This is like an underground organization, where everyone only knows who is behind them. If you want to send a message to agent K, you need to inform his next level from the publisher to K. So random access is not as good as array, order n time.

Insert the node

“Insert the tail“

Like arrays, insert nodes can be inserted at the head, middle, and tail. Tail insertion is easiest by pointing the “next” pointer of the last node to the newly inserted node.

“Insert the head“

There are two steps.

First, place the “Next” pointer of the new node to the original head node.

The first step is to make the new node the head of the list.

“The middle insert“

Again, there are two steps.

Place the “Next” pointer on the front node of the node at the insertion position to point to the new node specified for insertion.
Points the “Next” pointer of the new node to the node previously specified by the “Next” pointer of the front node.

Remove nodes

The deletion of singly linked lists also falls into three categories.

Remove the head
Central to delete
The tail to delete

The easiest way to delete a tail is to set the next-to-last node’s “next” pointer to NULL and set all nodes to NULL for garbage collector collection.

Delete the header, set the “next” node of the original linked list header node to the header node, and set the original header node to NULL for gc.

Delete the middle node and point the “Next” pointer of the front node of the node to be deleted to the “Next” pointer of the deleted node.

For delete and insert, it is clear as long as we draw the picture below.

Circular linked list

A circular list is a special type of single list. In fact, circular lists are quite simple. The only difference from a singly linked list is at the end. We know that the end pointer to a singly linked list points to an empty address, indicating that this is the last node. A pointer to the end of a circular list points to the start of the list. As you can see from my diagram of a circular list, it’s connected end to end like a loop, so it’s called a “circular” list.

With a single linked list, the main difference is that the tail node traverses to the head node easily.

Two-way linked list

The most common linked list in real development – bidirectional linked lists. The LinkedList in Java is a two-way LinkedList.

A singly linked list has only one direction, and each node has only one successor pointer, “Next,” to the next node. Bidirectionally linked lists have two Pointers, each with a “Next” pointer to the next node and a “prev” pointer to the front node.

As you can see, bidirectional lists require two additional Spaces to store the addresses of the successor and precursor nodes. So for the same amount of data, bidirectionally linked lists take up more space than single-chain lists, but have the advantage of being able to traverse both ways.

Bidirectional linked lists can support locating the leading nodes in O(1) time complexity, which also makes the operation of insertion and deletion of bidirectional linked lists simpler and more efficient than that of single linked lists in some cases.

“Insert time is O(1). Insert time is O(1). Insert time is O(1).“

There are two ways to delete an element from a list:

Delete the node whose value is equal to the given content.
Deletes the node to which the given pointer points.

In the first case, it is the same, no matter it is one-way or two-way, it is necessary to traverse from the beginning node to find the node to be deleted.

For the second case, we have found the node to delete, but delete a nodes q need to know its precursor, and singly linked lists is not support directly obtained precursor node, therefore, in order to find the precursor node, we still to traverse the list from head node, until p – > next = q, p is q precursors of nodes.

But for bidirectionally linked lists, this situation is advantageous. Because nodes in a bidirectional list already hold Pointers to their predecessors, they do not need to be traversed like single-linked lists. So, for the second case, single-linked list deletion takes O(n) time, whereas bidirectional lists only take O(1) time!

Bidirectional circular linked lists

Array and linked list performance comparison

Arrays and lists are linear data structures. Which one is better? In fact, there is no absolute good or bad data structure.

	To find the	update	delete	insert
An array of	O(1)	O(1)	O(n)	O(n)
The list	O(n)	O(1)	O(1)	O(1)

Array is easy to use, in the implementation of the use of continuous memory space, you can use the CPU cache mechanism, preread the array of data, so the access efficiency is higher. Linked lists are not stored consecutively in memory, so they are not CACHE-friendly and cannot be preread effectively.

Frequent insertion and deletion of linked lists also results in frequent memory requests and releases, which can easily lead to memory fragmentation and Garbage Collection (GC) if the Java language is used.

This article explains the theoretical principles and knowledge of linked lists, the next will be the code practice exercise.

Homework after class

How to implement an LRU cache elimination algorithm based on linked lists? The official number replies LRU backstage, you can get the answer.

Welcome to add group to discuss and share with us, we feedback the first time.