Find C one way linked list program, and ask the difference between one way linked list and bidirecti

Let's take an analogy. Think of a linked list node as a person, and a linked list pointer as a human hand (the left hand is the forward pointer, and the right hand is the backward pointer).

An acyclic one-way linked list looks like this: several people are lined up, each with their right hand pointing to the person to his right, and the person on the far right pointing to the air (null). If you want to find any person in this row, you have to look in the direction of your finger starting from the head of the row (linked list header).

A circular one-way linked list looks like this: a number of people form a circle, and each person raises his right hand to point at the person to his right, so that each person's right hand points to one person (and if there is only one person, his right hand points to himself). Starting with any one person, you can keep looping in the direction of your finger to find each person.

A non-cyclic doubly linked list looks like this: a number of people in a row, each of them raises their left hand to point to the person to his left, and each person raises his right hand to point to the person to his right, then the leftmost person's left finger points to air (null), and the rightmost person's right hand points to air (null). If you want to find a target person in this row, you can start with any person and try to find it in the left-hand direction, if you can't find it, you can continue to search in the right-hand direction until you find the target person.

A circular doubly linked list looks like this: a number of people sit in a circle, each of them raises their left hand to point to the person to his left, and each person raises their right hand to point to the person to his right, so that each person's left and right hands can point to one person (and if there is only one person, then his left and right hands are pointing at themselves). Whether you choose left-handed or right-handed directions, you can keep looping to find each one.

A linked list, like an array, is a data structure, and how you use it depends entirely on the needs of your application.

Linked lists have no connection to the C++ language itself. There are many languages that implement linked list data structures.

Let me talk about the difference between data and linked lists, which may help you get a feel for the use of linked lists.

An array is a continuous storage of elements in memory, and since each element occupies the same memory, you can quickly access any element in the array by subscripting. But if you want to add an element to the array, you need to move a large number of elements, make space for an element in memory, and then put the element you want to add in it. By the same token, if you want to delete an element, you also need to move a large number of elements to fill in the moved element.

Linked lists, on the contrary, are not stored sequentially in memory, but are linked together by pointers that exist in the elements. For example, the previous element has a pointer to the next element, and so on until the last element.

If you're going to access an element in a linked list, you'll need to start with the first element and work your way up to the location of the element you need. But adding and removing an element is very simple for a linked list data structure, just modify the pointer in the element.

As you can see from the above comparison, if your application needs to access data quickly, with little or no element insertion and deletion, you should use arrays; Conversely, if your application needs to insert and delete elements frequently, you'll need to use a linked list data structure. Then you can think for yourself about what kind of application is suitable for linked lists.

Also, it is recommended that you find a better book on data structures, which should have a detailed introduction to linked lists and the algorithms on them. The linked list itself is a complex data structure, and it includes many types, such as one-way linked lists, double-linked lists, trees, graphs, etc., which cannot be clearly introduced in one article.