GitHub source code sharing
Project homepage: github.com/gozhuyinglo…
Source: github.com/gozhuyinglo…
1. Introduction
We learned from the previous article “Array” that the storage structure of an array is a contiguous piece of memory, and each part of it may move as a whole when inserting or deleting elements. To avoid this linear overhead, we need to ensure that data can be stored discontinuously. This article introduces another data structure: linked lists.
2. Linked Lists
A linked list is a linear data structure whose physical storage structure is scattered. The logical order of data elements is realized by Pointers. A linked list consists of a series of nodes (each element of the list is called a node) that can be dynamically generated in memory.
Linked list features:
- Linked lists are stored in the form of nodes, so they are also called chained storage.
- Nodes can be continuously or discontinuously stored.
- The logical and physical order of nodes can be inconsistent
- Tables can be expanded (unlike arrays, which have to be reallocated)
Linked lists are divided into single linked lists, double linked lists and ring linked lists. The following examples are introduced one by one.
3. Singly Linked List
A singly linked list is also called a unidirectional list. Its nodes consist of two parts:
dataDomain: Data domain, used to store element datanextDomain: Point to the next node
The structure of a single linked list is shown below:
3.1 Operation of single linked list
All operations in a singly linked list start at head, which itself does not store elements. Its next points to the first node, and moves up the next chain. The next pointer of the tail node is empty, which is also the basis for judging the tail node.
This section describes how to insert and delete a node.
3.1.1 Inserting a Node
Inserting a new node into a single linked list can be done by adjusting the next pointer twice. As shown in the figure below, X is the new node, and next of A1 points to A2, then next of A1 points to X.
To insert from the tail node, point next of the tail node to the new node.
3.1.2 Deleting a Node
Deleting a node from a single linked list can be done by changing the next pointer of A1 to A3, as shown in the figure below. A2 is deleted and its memory space is automatically garbage collected.
If the tail node is deleted, the next pointer of the previous node is empty.
3.2 Code Implementation
We use Java code to implement a single linked list. The Node class stores a single Node of a single linked list, and the SinglyLinkedList class implements all operations of a single linked list. The SinglyLinkedList class is implemented using a lead node, the head node, which does not store data but simply marks the beginning of a single linked list.
public class SinglyLinkedListDemo {
public static void main(String[] args) {
Node node1 = new Node(1."Zhang");
Node node2 = new Node(3."Bill");
Node node3 = new Node(7."Fifty");
Node node4 = new Node(5."Daisy");
SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
System.out.println("----------- Add node (tail)");
singlyLinkedList.add(node1);
singlyLinkedList.add(node2);
singlyLinkedList.add(node3);
singlyLinkedList.add(node4);
singlyLinkedList.print();
System.out.println("----------- get a node");
Node node = singlyLinkedList.get(3);
System.out.println(node);
singlyLinkedList.remove(node3);
System.out.println("----------- Remove node");
singlyLinkedList.print();
System.out.println("----------- Modify node");
singlyLinkedList.update(new Node(5."Zhao six 2"));
singlyLinkedList.print();
System.out.println("----------- Add nodes in sequence");
Node node5 = new Node(4."Dynasty");
singlyLinkedList.addOfOrder(node5);
singlyLinkedList.print();
}
private static class SinglyLinkedList {
// The head node is the start of a singly linked list and does not store data
private Node head = new Node(0.null);
/** * adds the node to the end **@param node
*/
public void add(Node node) {
Node temp = head;
while (true) {
if (temp.next == null) {
temp.next = node;
break; } temp = temp.next; }}/** * Add nodes ** in sequence@param node
*/
public void addOfOrder(Node node) {
Node temp = head;
while (true) {
if (temp.next == null) {
temp.next = node;
break;
} else if(temp.next.key > node.getKey()){
node.next = temp.next;
temp.next = node;
break; } temp = temp.next; }}/** * get a node **@param key
* @return* /
public Node get(int key) {
if (head.next == null) {
return null;
}
Node temp = head.next;
while(temp ! =null) {
if (temp.key == key) {
return temp;
}
temp = temp.next;
}
return null;
}
/** * remove a node **@param node
*/
public void remove(Node node) {
Node temp = head;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.key == node.key) {
temp.next = temp.next.next;
break; } temp = temp.next; }}/** * Modifies a node **@param node
*/
public void update(Node node) {
Node temp = head.next;
while (true) {
if (temp == null) {
break;
}
if (temp.key == node.key) {
temp.value = node.value;
break; } temp = temp.next; }}/**
* 打印链表
*/
public void print(a) {
Node temp = head.next;
while(temp ! =null) { System.out.println(temp.toString()); temp = temp.next; }}}private static class Node {
private final int key;
private String value;
private Node next;
public Node(int key, String value) {
this.key = key;
this.value = value;
}
public int getKey(a) {
return key;
}
public String getValue(a) {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Node getNext(a) {
return next;
}
@Override
public String toString(a) {
return "Node{" +
"key=" + key +
", value='" + value + '\' ' +
'} '; }}}Copy the codeOutput result:
-- -- -- -- -- -- -- -- -- -- - add Node (tail) Node {key = 1, value = 'zhang'} Node {key = 3, value = 'bill'} Node {key = 7, value = 'Cathy'} Node {key = 5, Value = 'zhao six'} -- -- -- -- -- -- -- -- -- -- - to get a Node Node {key = 3, value = 'bill'} -- -- -- -- -- -- -- -- -- -- - to remove Node Node {key = 1, value = 'zhang'} Node {key = 3, Node value = 'bill'} {key = 5, value = 'zhao six'} -- -- -- -- -- -- -- -- -- -- - modify the Node Node {key = 1, value = 'zhang'} Node {key = 3, value = 'bill'} Node {key = 5, Value = 'zhao six 2} -- -- -- -- -- -- -- -- -- -- - in order to add the Node Node {key = 1, value =' zhang '} Node {key = 3, value = 'bill'} Node {key = 4, value = 'dynasty'} Node {key = 5, Value = 'zhao six 2}Copy the code3.3 Disadvantages of single linked lists
Through the analysis of the single linked list, it can be seen that the single linked list has the following shortcomings: (1) the search method of the single linked list can only be one direction (2) the single linked list can not delete itself, need to rely on a node for auxiliary operation.
These disadvantages can be solved by double-linked lists, as described below.
1. Key Linked List
A doubly linked list is also called a doubly linked list. Its nodes consist of three parts:
prevDomain: Used to point to the previous nodedataDomain: Data domain, used to store element datanextDomain: Point to the next node
The structure of a double-linked list is shown below:
4.1 Operation of double-linked lists
Double-linked lists can be operated from both ends, from the first node to the end with a next pointer, and from the last node to the head with a prev pointer.
This section describes how to insert and delete a node.
4.1.1 Inserting a Node
Inserting a new node into a double-linked list is accomplished by adjusting two prev Pointers and two next Pointers. As shown in the figure below, X is the new node, A1’s next points to X, X’s next points to A2, A2’s prev points to X, and X’s prev points to A1.
4.1.2 Deleting a Node
Removing a node from a double-linked list is accomplished by adjusting the prev pointer and the next pointer. As shown in the figure below, delete the A2 node and point A1’s next to A3 and A3’s prev to A1.
4.2 Code Implementation
We use Java code to implement a double-linked list. The Node class stores one Node of the double-linked list, and the DoublyLinkedList class implements all operation methods of the double-linked list. The DoublyLinkedList class is implemented with no lead node, where first is the first node and last is the last node. Both nodes are empty by default, and if there is only one element, both nodes refer to the same element.
public class DoublyLinkedListDemo {
public static void main(String[] args) {
DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
System.out.println("----------- add node from tail");
doublyLinkedList
.addToTail(new Node(1."Zhang"))
.addToTail(new Node(3."Bill"))
.addToTail(new Node(7."Fifty"))
.addToTail(new Node(5."Daisy"))
.print();
System.out.println("----------- Add node from header");
doublyLinkedList
.addToHead(new Node(0."Zhu Kaishan"))
.print();
System.out.println("----------- get a node");
System.out.println(doublyLinkedList.get(3));
System.out.println("----------- Remove node");
doublyLinkedList
.remove(new Node(3."Bill"))
.print();
System.out.println("----------- Modify node");
doublyLinkedList
.update(new Node(5."Zhao six 2")).print();
System.out.println("----------- Add nodes in sequence");
doublyLinkedList
.addOfOrder(new Node(4."Dynasty"))
.print();
}
private static class DoublyLinkedList {
private Node first = null; // The first node is the head of a double-linked list
private Node last = null; // tail node is the last node of the double-linked list
/** * adds ** from the tail@param node
*/
public DoublyLinkedList addToTail(Node node) {
if (last == null) {
first = node;
} else {
last.next = node;
node.prev = last;
}
last = node;
return this;
}
/** ** Add ** in order@param node
*/
public DoublyLinkedList addOfOrder(Node node) {
if (first == null) {
first = node;
last = node;
return this;
}
// Node is smaller than the head node. Set node to the head node
if (first.key > node.key) {
first.prev = node;
node.next = first;
first = node;
return this;
}
// Node is larger than the tail node. Set node to the tail node
if (last.key < node.key) {
last.next = node;
node.prev = last;
last = node;
return this;
}
Node temp = first.next;
while (true) {
if (temp.key > node.key) {
node.next = temp;
node.prev = temp.prev;
temp.prev.next = node;
temp.prev = node;
break;
}
temp = temp.next;
}
return this;
}
/** * adds ** from the header@param node
*/
public DoublyLinkedList addToHead(Node node) {
if (first == null) {
last = node;
} else {
node.next = first;
first.prev = node;
}
first = node;
return this;
}
/** * Get node **@param key
* @return* /
public Node get(int key) {
if (first == null) {
return null;
}
Node temp = first;
while(temp ! =null) {
if (temp.key == key) {
return temp;
}
temp = temp.next;
}
return null;
}
/** ** Remove node **@param node
*/
public DoublyLinkedList remove(Node node) {
if (first == null) {
return this;
}
// Remove the header node
if (first == node) {
first.next.prev = null;
first = first.next;
return this;
}
// Remove the tail node
if (last == node) {
last.prev.next = null;
last = last.prev;
return this;
}
Node temp = first.next;
while(temp ! =null) {
if (temp.key == node.key) {
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
break;
}
temp = temp.next;
}
return this;
}
/** * Modifies a node **@param node
*/
public DoublyLinkedList update(Node node) {
if (first == null) {
return this;
}
Node temp = first;
while(temp ! =null) {
if (temp.key == node.key) {
temp.value = node.value;
break;
}
temp = temp.next;
}
return this;
}
/**
* 打印链表
*/
public void print(a) {
if (first == null) {
return;
}
Node temp = first;
while(temp ! =null) { System.out.println(temp); temp = temp.next; }}}private static class Node {
private final int key;
private String value;
private Node prev; // point to the previous node
private Node next; // point to the next node
public Node(int key, String value) {
this.key = key;
this.value = value;
}
@Override
public String toString(a) {
return "Node{" +
"key=" + key +
", value='" + value + '\' ' +
'} '; }}}Copy the codeOutput result:
-- -- -- -- -- -- -- -- -- -- - from the tail added Node Node {key = 1, value = 'zhang'} Node {key = 3, value = 'bill'} Node {key = 7, value = 'Cathy'} Node {key = 5, Value = 'zhao six'} -- -- -- -- -- -- -- -- -- -- - from the head to add Node Node {key = 0, value = 'Zhu Kaishan'} Node {key = 1, value = 'zhang'} Node {key = 3, value = 'bill'} Node {key = 7, Node value = 'Cathy'} {key = 5, value = 'zhao six'} -- -- -- -- -- -- -- -- -- -- - to get a Node Node {key = 3, value = 'bill'} -- -- -- -- -- -- -- -- -- -- - to remove Node Node {key = 0, The Node value = 'Zhu Kaishan} {key = 1, value =' zhang '} Node {key = 7, value = 'Cathy'} Node {key = 5, value = 'zhao six'} -- -- -- -- -- -- -- -- -- -- - modify the Node Node {key = 0, The Node value = 'Zhu Kaishan} {key = 1, value =' zhang '} Node {key = 7, value = 'Cathy'} Node {key = 5, value = 'zhao six 2} -- -- -- -- -- -- -- -- -- -- - in order to add the Node Node {key = 0, } Node{key=1, value=' zhang3 '} Node{key=4, value=' wang5 '} Node{key=7, value=' wang5 '} Node{key=5, value=' wang6 '}Copy the code5. Circular Linked List
Circular linked lists are also called circular linked lists. This paper describes one-way circular linked lists. The only difference between them and single linked lists is that the next of the tail node is no longer empty, so it points to the head node, thus forming a ring.
The structure of a circular list is shown below:
5.1 Joseph problem
Joseph problem: Sometimes called Josephus permutation, is a problem in computer science and mathematics. In computer programming algorithms, similar problems are called Joseph rings. Also known as “lost handkerchief problem”.
Quoted from Baidu Baike:
Josephus, the famous Jewish historian, is said to have told the following story: After the Roman occupation of Joe tower pat, 39 jews and Josephus and his friend hiding in a hole, 39 decided jews would rather die don’t was caught by the enemy, then made a suicide, 41 people arranged in a circle, start from 1 individual number off, each number off to third person would have to commit suicide, and then the next number off again, Until everyone committed suicide. Josephus and his friends, however, did not want to comply. Start with one person, pass k-2 people (since the first person has already been passed), and kill the KTH person. And then you go over k minus one person and you kill the k person. The process continues along the circle until only one person is left, and that person can continue to live. The question is, given the sum, where to stand in order to avoid execution in the first place. Josephus told his friend to pretend to obey first, and he escaped the game of death by placing him and his friend in positions sixteen and thirty-one.
In the Problem of The Game of Numbers, a 17th-century French mathematician named Gaspar told a story about 15 religious and 15 non-religious men who were in trouble at sea. Half of them had to be thrown into the sea so that the rest could survive. Thirty people form a circle, counting off the first one, throwing the ninth one into the sea, and so on until there are only fifteen left. How to arrange it so that every time a non-believer is thrown into the sea.
Problem analysis and algorithm design
Joseph’s problem is not difficult, but there are many ways to solve it; And there’s a lot of variation. Here is a way to do it.
The 30 people in a circle inspired us to represent it as a circular chain, which can be formed using structural arrays. There are two members in the structure, one is a pointer to the next person, to form a ring chain; The second is whether the person was thrown into the sea, a mark of 1 means still on the ship. Everyone who has not been thrown into the sea is counted from the first person. At each count of 9, the mark in the structure is changed to 0 to indicate that the person has been thrown into the sea. And so on until 15 people are thrown into the sea.
5.2 Code Implementation
We use Java code to implement a circular linked list and list the nodes in the Order of Joseph’s problems.
public class CircularLinkedListDemo {
public static void main(String[] args) {
CircularLinkedList circularLinkedList = new CircularLinkedList();
System.out.println("----------- Add 10 nodes");
for (int i = 1; i <= 10; i++) {
circularLinkedList.add(new Node(i));
}
circularLinkedList.print();
System.out.println("----------- in order of Joseph's questions.");
circularLinkedList.josephusProblem(3);
}
private static class CircularLinkedList {
private Node first = null; // The header node, the first node
/** * Add nodes and point next of the newly added node to the head to form a ring **@param node
* @return* /
public void add(Node node) {
if (first == null) {
first = node;
first.next = first;
return;
}
Node temp = first;
while (true) {
if (temp.next == null || temp.next == first) {
temp.next = node;
node.next = first;
break; } temp = temp.next; }}/** * count from the first element to num, and then count from the next until all elements are counted **@paramNum indicates the number of times */ is reported
public void josephusProblem(int num) {
Node currentNode = first;
// Point the current node to the last node
do {
currentNode = currentNode.next;
} while(currentNode.next ! = first);// Start to exit
while (true) {
// The current node must point to the node before the node to be exited (not required for bidirectional ring queue)
for (int i = 0; i < num - 1; i++) {
currentNode = currentNode.next;
}
System.out.printf("%s\t", currentNode.next.no);
if(currentNode.next == currentNode){
break; } currentNode.next = currentNode.next.next; }}/** * output node */
public void print(a) {
if (first == null) {
return;
}
Node temp = first;
while (true) {
System.out.printf("%s\t", temp.no);
if (temp.next == first) {
break; } temp = temp.next; } System.out.println(); }}private static class Node {
private final int no;
private Node next; // point to the next node
public Node(int no) {
this.no = no;
}
@Override
public String toString(a) {
return "Node{" +
"no=" + no +
'} '; }}}Copy the codeOutput result:
----------- Add 10 nodes 1 2 3 4 5 6 7 8 9 10 ----------- list 3 6 9 2 7 1 8 5 10 4 in the order of Joseph questionsCopy the codeGet more content
Wechat search: code nong StayUp
Personal homepage: GoZhuyinglong.github. IO