This is the 12th day of my participation in the First Wenwen Challenge 2022.First challenge in 2022.

Learn data structures – linked lists

The list

A linked list is a data structure used to represent a series of nodes. In a one-way linked list, each node points to the next node in the list. In a bidirectional list, each node has a pointer to both the previous and the next node.

The following figure depicts a bidirectional linked list.

Unlike arrays, a specific index of a linked list cannot be accessed in constant time complexity. That means if you want to access the first digit in the listElement, which requires iterative accessAn element.

The beauty of linked lists is that you can add and remove elements in constant time. This is useful for certain programs.

Create a list

The following code implements a very basic one-way linked list.

Instead of having a LinkedList data structure, this implementation accesses the list through a reference to Node, the list’s head Node. Be careful when implementing linked lists in this way. What if multiple objects need to reference the list and the list head node changes? Some objects may still point to the old head node.

You can optionally implement a LinkedList class to encapsulate the Node class. This class contains only one member variable: the head Node Node. Doing so can solve the above problems to a large extent.

Remember: When you come across a linked list question in an interview, be sure to find out whether it is a one-way list or a two-way list.

Deletes a node in a one-way linked list

Deleting a node from a one-way linked list is very simple. Given a node n, find its forward node prev and set prev.next to n.next. If this is a bidirectional list, update n.ext by setting n.ext. Prev to n.rev. Of course, two things must be noted :(1) check for null Pointers; (2) Update the head or tail pointer if necessary.

In addition, if you are using C, C++, or other languages that require developers to manage their own memory, you should also consider freeing memory for deleted nodes.

The “fast line pointer” technique

The “fast line pointer” (or second pointer) is a very common technique when dealing with linked list problems. Fast row pointer refers to the use of two Pointers to access a linked list iteratively at the same time, but one of them is ahead of the other. The “fast” pointer is usually a few steps ahead, or a fixed number of steps away from the “slow” pointer.

For example, suppose you have a linked list A1 -> A2 ->… ->an->b1->b2->… -> BN, you want to rearrange it into a1-> B1 -> A2 -> B2 ->… – > the an – > bn. Also, you don’t know the length of the list (but make sure it’s even).

You can use two Pointers, where P1 (fast pointer) moves forward two steps at a time, while P2 moves one step at a time. When P1 reaches the end of the list, P2 is in the middle of the list. Then, move P1 and P2 backward step by step from tail to head, and insert the node pointing to P2 behind the node pointing to P1.

Recursive problem

Recursion is used for many linked list problems. When you hit a brick wall with linked lists, try recursion. We won’t go into recursion in depth here, but there will be a section on recursion later.

Of course, it’s important to note that the recursive algorithm at least occupiesThe space in whichIs the number of layers of recursive calls. In fact, all recursive algorithmscanTo an iterative approach, which can be much more complex to implement.