Write in front
Modular programming is a must-see for most beginners, and then you may move towards structured programming. Linked lists are a typical structural pattern. The emergence of them overcomes the defect that arrays must know the size in advance, and they don’t understand? You just need to remember that the linked list structure is very awesome. Learning this structure has greatly improved our logical thinking.
What is a linked list structure?
A linked list is a non-continuous and non-sequential storage structure on a physical storage unit. For example, A->B->C, we can understand this structure as A connects B, B connects C. We call this structure linked list structure. By the way, the train car is actually the best explanation of the structure of the linked list
Why do you need a linked list structure?
Anyone who has studied computer knows that Arrays are often used and easy to cut, but there are also problems. First, the array must know the space size (int[] age = new int[100], the length must be declared), and secondly, the operation efficiency of inserting and deleting between elements is very inefficient (how to insert an element in the middle of the array?).
The emergence of linked lists perfectly solved these problems.
How to implement linked list
First we need to declare a structure
//Linked list structure: Construct node - Connect node//Template
class Node
{
public int num;
//Point to the next element public Node next;
}
//Linked list structure: Construct node - Connect node//Template
class Node
{
public int num;
//Point to the next element public Node next;
}
We can regard the above structure as a gift box that can store plastic sculpting values.
Then we created a Mr. MyList, who used Node to store plastic surgery items and used a linked list structure!
class MyList
{
public Node currentNode;
public Node point;
public MyList()
{
currentNode = new Node();
}
//Storage items public void Add(int value)
{
//first if(point == null)
{
= value;
point = currentNode;
}
else //2 3 4... times {
Node temp = new Node();
= value;
= temp;
//Update pointer point = temp;
}
}
}
class MyList
{
public Node currentNode;
public Node point;
public MyList()
{
currentNode = new Node();
}
//Storage items public void Add(int value)
{
//first if(point == null)
{
= value;
point = currentNode;
}
else //2 3 4... times {
Node temp = new Node();
= value;
= temp;
//Update pointer point = temp;
}
}
}
Then, we can test it on the client side:
public static void Main (string[] args)
{
MyList<int> mList = new MyList<int>();
//Add elements (1);
(11);
(111);
(1111);
while( != null)
{
();
= ;
}
}
public static void Main (string[] args)
{
MyList<int> mList = new MyList<int>();
//Add elements (1);
(11);
(111);
(1111);
while( != null)
{
();
= ;
}
}
A plastic surgery collection we defined ourselves is OK. It has two advantages: it can store as many elements as possible! Convenient to insert and delete elements.
Definition and simple operation of two-way linked lists:
Two-way linked lists are actually an improvement in single linked lists. When we operate on a single linked list, sometimes when you want to operate on the direct predecessor of a certain node, you must start looking at the table header. This is limited by the structure of single linked list nodes. Because each node in a single linked list has only one link domain that stores direct successor node addresses, can we define a double-link domain node structure that has both a link domain that stores direct successor node addresses and a link domain that stores direct predecessor node addresses? This is a two-way linked list. In a bidirectional linked list, in addition to the data domain, nodes also contain two link domains. One stores the direct successor node address, which is generally called the right link domain; the other stores the direct predecessor node address, which is generally called the left link domain.
namespace DounlyLinkedlist
{
//Define the nodes of the bidirectional linked list public class Node
{
public Object Element;
public Node FLink;
public Node BLink;
public Node()
{
Element = null;
FLink = null;
BLink = null;
}
public Node(Object element)
{
Element = element;
FLink = null;
BLink = null;
}
}
//Class of linked list operations public class LinkedList
{
public Node Header;
public LinkedList()
{
Header = new Node("Header");
= null;
= null;
}
//Find nodes private Node Find(Object item)
{
Node Current = new Node();
Current = Header;
while ( != item)
{
Current = ;
}
return Current;
}
//Insert node public void InsertNode(Object item,Object postionItem)
{
Node Current = new Node();
Node NewItem = new Node(item);
Current = Find(postionItem);
if (Current != null)
{
= ;
= Current;
= NewItem;
}
}
//Delete node public void Remove(Object item)
{
Node P = Find(item);
if ( != null)
{
= ;
= ;
= null;
= null;
}
}
//Find the last node element of the bidirectional linked list private Node FindLast()
{
Node Current = new Node();
Current = Header;
while (!( == null))
{
Current = ;
}
return Current;
}
//Reversely print the bidirectional link table public void PrintReverse()
{
Node Current = new Node();
Current = FindLast();
while (!( == null))
{
();
Current = ;
}
}
//Print the bidirectional link table public void Print()
{
Node Current = new Node();
Current = Header;
while (!( == null))
{
();
Current = ;
}
}
}
}
Linked list application scenarios
Application scenarios: collections (dynamic arrays), snakes, map cycle generation, slot machine effects, etc. Linked lists can help us accomplish many things.