dynamic chain
Single linked list:
//Head node refers to the first node in the linked list, which can be divided into real head node and virtual head node;
(1) Real head node: the first node is used to store data (usually the real head node is used).
(2) Virtual head node: the first node cannot store data.
(3) Header pointer: it is just a reference variable that stores the address of the header node. There is no precursor node and there are successors.
(4) Tail pointer: the same head pointer is just the pointer to the last node in the linked list. The tail points to null. There is a precursor but no successor.
To add elements to a single linked list:
To insert an element at element 3, first set the pointer p so that p points to the previous element to be inserted. For example, to insert an element at element 3 in the figure, first let p find element 2 because the address of element 3 exists in element 2, and then give the address of element 2 to the new element so that the new element points to element 3 Then let element 2 point to the new element.
//For understanding with the help of table building, there is actually no element of corner mark.
Delete elements from single linked list:
//Delete element 4, replace the address of element 5 stored in element 4 with the address of element 4 originally stored in element 3, and leave the address of element 4 blank. Directly, let element 3 directly point to element 5 and release element 4.
//If both the head pointer and the tail pointer point to the same element, when deleting, just set the head pointer and the tail pointer to null respectively.
Code part:
//Define the linked list class, but there is another node class, so we need to use the internal class to define the node. Here, the linked list is in the outermost layer and the node is in the interior, so the linked list is an external class and the node is an internal class.
//If you use the toString method, because if you don't use toString, the result is the name of the data, not the data itself, so you use the toString method to get the data content. The print node is actually the data stored in the print node.
//Here is a dynamic linked list, which is automatically expanded, so you don't need to set the default value.
//Unidirectional linked list
public class LinkedSinglyList<E> implements List<E> {
//Define node object
private class Node {
E data; //Data domain
Node next; //Pointer field
public Node(){
this(null,null);
}
public Node(E data) {
this(data,null);
}
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return data.toString();
}
}
private Node head; //Head pointer
private Node tail; //Tail pointer
private int size; //Number of elements
public LinkedSinglyList() {
head = null;
tail = null;
size = 0;
}
public LinkedSinglyList(E[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("arr is null");
}
for (int i = 0; i < arr.length; i++) {
add(arr[i]);
}
}
@Override
public void add(E element) {
add(size, element);
}
@Override
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add index out of range");
}
Node n = new Node(element);
if (size == 0) {
head = n;
tail = n;
} else if (index == 0) {
n.next = head;
head = n;
} else if (index == size) {
tail.next = n;
tail = n;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
n.next = p.next;
p.next = n;
}
size++;
}
@Override
public void remove(E element) {
int index = indexOf(element);
if (index != -1) {
remove(index);
}
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove index out of range");
}
E ret = null;
if (size == 1) {
ret = head.data;
head = null;
tail = null;
} else if (index == 0) {
Node n = head;
ret = n.data;
head = n.next;
n.next = null;
} else if (index == size - 1) {
Node p = head;
while (p.next != tail) {
p = p.next;
}
ret = tail.data;
p.next = null;
tail = p;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
Node n = p.next;
ret = n.data;
p.next = n.next;
n.next = null;
}
size--;
return ret;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
if (index == 0) {
return head.data;
} else if (index == size - 1) {
return tail.data;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
}
}
@Override
public E set(int index, E element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
E ret = null;
if (index == 0) {
ret = head.data;
head.data = element;
} else if (index == size - 1) {
ret = tail.data;
tail.data = element;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
ret = p.data;
p.data = element;
}
return ret;
}
@Override
public int size() {
return size;
}
@Override
public int indexOf(E element) {
Node p = head;
int index = 0;
while (!p.data.equals(element)) {
p = p.next;
index++;
if (p == null) {
return -1;
}
}
return index;
}
@Override
public boolean contains(E element) {
return indexOf(element) != -1;
}
@Override
public boolean isEmpty() {
return size == 0 && head == null && tail == null;
}
@Override
public void clear() {
head = null;
tail = null;
size = 0;
}
@Override
public void sort(Comparator<E> c) {
if (c == null) {
throw new IllegalArgumentException("comparator can not be null");
}
//Insert sort o here (n ^ 3)
/*
for (int i = 1; i < size; i++) {
E e = get(i);
int j = 0;
for (j = i; j > 0 && c.compare(get(j - 1), e) > 0; j--) {
set(j, get(j - 1));
}
set(j, e);
}
*/
if (size == 0 || size == 1) {
return;
}
Node nodeA = head;
Node nodeB = nodeA.next;
while (true) {
while (true) {
if (c.compare(nodeA.data, nodeB.data) > 0) {
swap(nodeA, nodeB);
}
if (nodeB == tail) {
break;
}
nodeB = nodeB.next;
}
if (nodeA.next == tail) {
break;
}
nodeA = nodeA.next;
nodeB = nodeA.next;
}
}
private void swap(Node nodeA, Node nodeB) {
E temp = nodeA.data;
nodeA.data = nodeB.data;
nodeB.data = temp;
}
@Override
public List<E> subList(int fromIndex, int toIndex) {
//0 <= fromIndex <= toIndex <= size - 1 [fromIndex,toIndex]
if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1");
}
LinkedSinglyList<E> list = new LinkedSinglyList<>();
Node nodeA = head;
for (int i = 0; i < fromIndex; i++) {
nodeA = nodeA.next;
}
Node nodeB = head;
for (int i = 0; i < toIndex; i++) {
nodeB = nodeB.next;
}
Node p = nodeA;
while (true) {
list.add(p.data);
if (p == nodeB) {
break;
}
p = p.next;
}
return list;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
if (isEmpty()) {
sb.append(']');
} else {
Node p = head;
while (true) {
sb.append(p.data);
if (p == tail) {
sb.append(']');
break;
}
sb.append(',');
sb.append(' ');
p = p.next;
}
}
return sb.toString();
}
@Override
public Iterator<E> iterator() {
return new LinkedSinglyListIterator();
}
class LinkedSinglyListIterator implements Iterator<E> {
private Node cur = head;
@Override
public boolean hasNext() {
return cur != null;
}
@Override
public E next() {
E ret = cur.data;
cur = cur.next;
return ret;
}
}
}
One way circular linked list
If the pointer to the last node of the single linked list points to the head of the linked list instead of to NULL，Then it constitutes a one-way circular linked list.
//Different from the single linked list, the single linked list allows the tail pointer to point to null, while the one-way circular linked list allows the tail pointer to point to the head pointer to complete the cycle.
Add element:
//Adding is similar to adding a single linked list. Set the pointer p to point to the previous element to be inserted, because the previous element has the address of the current element to be inserted. Give the address of the previous element to the new element, let the new element point to the current element to be inserted, and then let the previous element point to the new element.
Delete element:
//To delete an element, you need to set a null pointer. If you delete a header element, first pass the content of the header element to the null pointer, then let the header pointer point to the next element of the null pointer, and then let the null pointer point to null. Delete the tail and let the null pointer traverse. Because it is one-way, you must traverse to find the previous element of the tail element, The random operation is the same as deleting the header pointer;
//If there is only one element, you can directly make the head pointer and tail pointer point to null;
//If you delete other elements, you also need to traverse to the element before the element to be deleted and delete it with a null pointer;
code:
//One way circular linked list
public class LinkedSinglyCircularList<E> implements List<E> {
//Define node object
private class Node {
E data; //Data domain
Node next; //Pointer field
public Node(){
this(null,null);
}
public Node(E data) {
this(data,null);
}
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return data.toString();
}
}
private Node head; //Head pointer
private Node tail; //Tail pointer
private int size; //Number of elements
public LinkedSinglyCircularList() {
head = null;
tail = null;
size = 0;
}
public LinkedSinglyCircularList(E[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("arr is null");
}
for (int i = 0; i < arr.length; i++) {
add(arr[i]);
}
}
@Override
public void add(E element) {
add(size, element);
}
@Override
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add index out of range");
}
Node n = new Node(element);
if (size == 0) {
head = n;
tail = n;
tail.next = head; //new code
} else if (index == 0) {
n.next = head;
head = n;
tail.next = head; //new code
} else if (index == size) {
n.next = tail.next; //new code
tail.next = n;
tail = n;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
n.next = p.next;
p.next = n;
}
size++;
}
@Override
public void remove(E element) {
int index = indexOf(element);
if (index != -1) {
remove(index);
}
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove index out of range");
}
E ret = null;
if (size == 1) {
ret = head.data;
head = null;
tail = null;
} else if (index == 0) {
Node n = head;
ret = n.data;
head = n.next;
n.next = null;
tail.next = head; //new code
} else if (index == size - 1) {
Node p = head;
while (p.next != tail) {
p = p.next;
}
ret = tail.data;
p.next = tail.next; //change code
tail = p;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
Node n = p.next;
ret = n.data;
p.next = n.next;
n.next = null;
}
size--;
return ret;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
if (index == 0) {
return head.data;
} else if (index == size - 1) {
return tail.data;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
}
}
@Override
public E set(int index, E element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get index out of range");
}
E ret = null;
if (index == 0) {
ret = head.data;
head.data = element;
} else if (index == size - 1) {
ret = tail.data;
tail.data = element;
} else {
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
ret = p.data;
p.data = element;
}
return ret;
}
@Override
public int size() {
return size;
}
@Override
public int indexOf(E element) {
Node p = head;
int index = 0;
while (!p.data.equals(element)) {
p = p.next;
index++;
if (p == head) { //change code
return -1;
}
}
return index;
}
@Override
public boolean contains(E element) {
return indexOf(element) != -1;
}
@Override
public boolean isEmpty() {
return size == 0 && head == null && tail == null;
}
@Override
public void clear() {
head = null;
tail = null;
size = 0;
}
@Override
public void sort(Comparator<E> c) {
if (c == null) {
throw new IllegalArgumentException("comparator can not be null");
}
if (size == 0 || size == 1) {
return;
}
Node nodeA = head;
Node nodeB = nodeA.next;
while (true) {
while (true) {
if (c.compare(nodeA.data, nodeB.data) > 0) {
swap(nodeA, nodeB);
}
if (nodeB == tail) {
break;
}
nodeB = nodeB.next;
}
if (nodeA.next == tail) {
break;
}
nodeA = nodeA.next;
nodeB = nodeA.next;
}
}
private void swap(Node nodeA, Node nodeB) {
E temp = nodeA.data;
nodeA.data = nodeB.data;
nodeB.data = temp;
}
@Override
public List<E> subList(int fromIndex, int toIndex) {
if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1");
}
LinkedSinglyList<E> list = new LinkedSinglyList<>();
Node nodeA = head;
for (int i = 0; i < fromIndex; i++) {
nodeA = nodeA.next;
}
Node nodeB = head;
for (int i = 0; i < toIndex; i++) {
nodeB = nodeB.next;
}
Node p = nodeA;
while (true) {
list.add(p.data);
if (p == nodeB) {
break;
}
p = p.next;
}
return list;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
if (isEmpty()) {
sb.append(']');
} else {
Node p = head;
while (true) {
sb.append(p.data);
if (p == tail) {
sb.append(']');
break;
}
sb.append(',');
sb.append(' ');
p = p.next;
}
}
return sb.toString();
}
@Override
public Iterator<E> iterator() {
return new LinkedSinglyCircularListIterator();
}
class LinkedSinglyCircularListIterator implements Iterator<E> {
private Node cur = head;
private boolean flag = true; //Is it on the first lap
@Override
public boolean hasNext() {
if (isEmpty()) {
return false;
}
return flag;
}
@Override
public E next() {
E ret = cur.data;
cur = cur.next;
if (cur == head) {
flag = false;
}
return ret;
}
}
//Joseph Ring problem
public void josephusLoop() {
if (size <= 2) {
return;
}
Node p = head;
while (size != 2) {
p = p.next;
Node del = p.next;
if (del == head) {
head = del.next;
} else if (del == tail) {
tail = p;
}
p.next = del.next;
del.next = null;
p = p.next;
size--;
}
}
//Linked list inversion problem
public void reverse() {
if (size == 0 || size == 1) {
return;
}
Node dummpyHead = new Node(); //Virtual head node
Node p = head;
for (int i = 0; i < size; i++) {
Node n = new Node(p.data);
if (dummpyHead.next == null) {
tail = n;
}
n.next = dummpyHead.next;
dummpyHead.next = n;
p = p.next;
}
head = dummpyHead.next;
}
}
Application of single linked list - Joseph problem: (Joseph Ring)
//Joseph Ring problem
public void josephusLoop() {
if (size <= 2) {
return;
}
Node p = head;
while (size != 2) {
p = p.next;
Node del = p.next;
if (del == head) {
head = del.next;
} else if (del == tail) {
tail = p;
}
p.next = del.next;
del.next = null;
p = p.next;
size--;
}
}
Let's start from the node and delete the element every time to the third node. As shown in the figure, starting from node 1, delete node 3, node 6, node 4, node 2, and finally the remaining node 5 and node 1.
code:
Linked list inversion problem:
//Linked list inversion problem
public void reverse() {
if (size == 0 || size == 1) {
return;
}
Node dummpyHead = new Node(); //Virtual head node
Node p = head;
for (int i = 0; i < size; i++) {
Node n = new Node(p.data);
if (dummpyHead.next == null) {
tail = n;
}
n.next = dummpyHead.next;
dummpyHead.next = n;
p = p.next;
}
head = dummpyHead.next;
}
}
Every seven games:
code:
//Every seven games
/*
Enter the number of players
Enter which player to start with
Enter the number from which the player starts
Enter a total of several numbers to play
Print out all the numbers that each player will report
*/
public class SevenGame {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print(">>>Please enter the number of players:");
int playerCount = input.nextInt();
System.out.print(">>>Please enter which player to start with:");
int beginPlayer = input.nextInt();
System.out.print(">>>Please enter which number to start with:");
int beginNumber = input.nextInt();
System.out.print(">>>Please enter the maximum number:");
int maxNumber = input.nextInt();
//Create a collection of players
LinkedSinglyCircularList<ArrayList<String>> list = new LinkedSinglyCircularList<>();
//Create player objects separately
for (int i = 0; i < playerCount; i++) {
list.add(new ArrayList<>());
}
//Starting player's corner marker
int index = beginPlayer - 1;
//Give the numbers to each player in turn
for (int num = beginNumber; num <= maxNumber; num++) {
list.get(index++ % playerCount).add(getAnswer(num));
}
for (int i = 0; i < list.size(); i++) {
System.out.println("The first" + (i + 1) + "Players:" + list.get(i));
}
}
private static String getAnswer(int num) {
if (num % 7 == 0 || (num + "").contains("7")) {
return "too";
}
return num + "";
}
}
Bidirectional circular linked list
Each node has two pointers to the predecessor node and the successor node respectively; Bidirectional linked list, also known as double linked list, is a kind of linked list. There are two pointers in each data node, pointing to the direct successor and direct precursor respectively. Therefore, starting from any node in the two-way linked list, you can easily access its predecessor node and successor node. Generally, we construct a two-way circular linked list.
Add element:
(1) : add elements from beginning to end:
(2) : add elements in the middle:
Some codes are shown in the figure:
@Override
public void add(E element) {
add(size, element);
}
@Override
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add index out of range");
}
Node n = new Node(element);
if (size == 0) {
head = n;
tail = n;
tail.next = head;
head.pre = tail;
} else if (index == 0) {
n.pre = head.pre;
n.next = head;
head.pre = n;
head = n;
tail.next = head;
} else if (index == size) {
n.next = tail.next;
tail.next = n;
n.pre = tail;
tail = n;
head.pre = tail;
} else {
Node p, q;
if (index <= size / 2) {
p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
q = p.next;
p.next = n;
n.pre = p;
q.pre = n;
n.next = q;
} else {
p = tail;
for (int i = size - 1; i > index; i--) {
p = p.pre;
}
q = p.pre;
q.next = n;
n.pre = q;
n.next = p;
p.pre = n;
}
}
size++;
}
Delete element:
(1) Delete elements from beginning to end:
(2) Middle delete element:
Some codes are shown in the figure:
@Override
public void remove(E element) {
int index = indexOf(element);
if (index != -1) {
remove(index);
}
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove index out of range");
}
E ret = null;
Node node;
if (size == 1) {
ret = head.data;
head = null;
tail = null;
} else if (index == 0) {
ret = head.data;
node = head.next;
head.next = null;
node.pre = head.pre;
head.pre = null;
head = node;
tail.next = head;
} else if (index == size - 1) {
ret = tail.data;
node = tail.pre;
tail.pre = null;
node.next = tail.next;
tail.next = null;
tail = node;
head.pre = tail;
} else {
Node p, q, r;
if (index <= size / 2) {
p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
q = p.next;
r = q.next;
ret = q.data;
p.next = r;
r.pre = p;
q.next = null;
q.pre = null;
} else {
p = tail;
for (int i = size - 1; i > index + 1; i--) {
p = p.pre;
}
q = p.pre;
r = q.pre;
ret = q.data;
r.next = p;
p.pre = r;
q.next = null;
q.pre = null;
}
}
size--;
return ret;
}
//Pay attention to the corresponding relationship. Don't make a mistake!!!
Let's talk about the sorting method:
We can use insert sort or other methods:
@Override
public void sort(Comparator<E> c) {
//An exception is thrown for empty judgment
if (c == null) {
throw new IllegalArgumentException("comparator can not be null");
}
//The valid length is empty or one
if (size == 0 || size == 1) {
return;
}
for (Node nodeA = head.next; nodeA != head; nodeA = nodeA.next) {
E e = nodeA.data;
Node nodeB;
Node nodeC;
for (nodeB = nodeA, nodeC = nodeB.pre; nodeC != tail && c.compare(nodeC.data, e) > 0; nodeB = nodeB.pre, nodeC = nodeC.pre) {
nodeB.data = nodeC.data;
}
nodeB.data = e;
}
}
We also need classes that implement double ended queues:
The code is as follows:
//Method of double ended queue
@Override
public void addFirst(E element) {
add(0, element);
}
@Override
public void addLast(E element) {
add(size, element);
}
@Override
public E removeFirst() {
return remove(0);
}
@Override
public E reomveLast() {
return remove(size - 1);
}
@Override
public E getFirst() {
return get(0);
}
@Override
public E getLast() {
return get(size - 1);
}
//Stack method
@Override
public void push(E element) {
addLast(element);
}
@Override
public E pop() {
return reomveLast();
}
@Override
public E peek() {
return getLast();
}
//Queue method
@Override
public void offer(E element) {
addLast(element);
}
@Override
public E poll() {
return removeFirst();
}
@Override
public E element() {
return getFirst();
}
}
On the definition of linked list node
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val; this.next =next;
}
}