Simulated single-linked table
Linear table:
Linear tables (also called sequential tables) are the most basic, simplest and most commonly used data structures.
The relationship between data elements in a linear table is a one-to-one relationship, that is, except for the first and last data elements, other data elements are connected to the end.
The logical structure of linear tables is simple, which is easy to implement and operate.
In practical applications, linear tables are used in the form of special linear tables such as stacks, queues, and strings.
The basic characteristics of linear structure are:
1. There must be a unique "first element" in the collection;
2. There must be a unique "last element" in the collection;
3. Except for the last element, there is a unique successor (latest item);
4. Except for the first element, there is a unique front drive (front piece).
Linked list: linked list
A linked list is a non-continuous and non-sequential storage structure on a physical storage unit. The logical order of data elements is that each data item implemented through the pointer link order in the linked list is contained in a "link point".
A link is an object of a class, and this type can be called Link. There are many similar links in the linked list, and each link contains a field next referenced to the next link.
The linked list object itself holds a reference to the first link node. (If there is no first, it cannot be located)
A linked list cannot directly access data items like an array (using subscripts), but needs to be positioned with the relationship between data, that is, access the next link referenced by the link node, and then the next one, until the required data is accessed and the time complexity of inserting and deleting the required data at the head is O(1), because only the reference pointing is necessary to find, delete the specified node, and insert it after the specified node. These operations require an average of searching half of the nodes in the linked list, with an efficiency of O(N).
Single linked list:
A linear table is represented by "sequence of nodes" and is called a linear linked list (single linked list)
It is a chain access data structure, using a set of storage units with arbitrary addresses to store data elements in a linear table. (This set of memory cells can be either continuous or discontinuous)
The structure of the link node:
Data field data that stores node values; pointer field (chain field) that stores node reference next
The linked list links the n nodes of the linear table together in their logical order through the link domain of each node.
A linked list with only one link field per node is called a single link list. In one direction, there are only references to subsequent nodules.
/** * Single linked list: header insertion method and first exit* The left side of the linked list is called the chain head and the right side is called the chain tail. * The header insert method to build a single linked list is obtained by viewing the right end of the linked list as fixed, and the linked list continues to extend to the left. * The first thing that comes from the header insertion method is the tail node* @author stone */ public class SingleLinkedList<T> { private Link<T> first; //The first node public SingleLinkedList() { } public boolean isEmpty() { return first == null; } public void insertFirst(T data) {// Insert into the head of the chain Link<T> newLink = new Link<T>(data); newLink.next = first; //The next of the new node points to the previous node first = newLink; } public Link<T> deleteFirst() {//Delete the chain header Link<T> temp = first; first = first.next; //Change the first node to return temp; } public Link<T> find(T t) { Link<T> find = first; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link<T> delete(T t) { if (isEmpty()) { return null; } else { if (first.data.equals(t)) { Link<T> temp = first; first = first.next; //Change the first node to the next node return temp; } } Link<T> p = first; Link<T> q = first; while (!p.data.equals(t)) { if (p.next == null) {//Sign up to the end of the chain but not found return null; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//Transip System.out.println("List (first-->last):"); Link<T> current = first; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//Inverse traversal Link<T> p = first, q = first.next, t; while (q != null) {//Pointer is reversed, the traversed data order is backward t = q.next; //no3 if (p == first) {// When it is the original header, the .next of the head should be empty p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //In the if in the loop above, first.next is empty, and when q is null and does not execute the loop, p is the original most data item. After inversion, p is assigned to first first = p; displayList(); } class Link<T> {//link point T data; //Data field Link<T> next; //Subsequent pointer, node chain domain Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { SingleLinkedList<Integer> list = new SingleLinkedList<Integer>(); list.insertFirst(33); list.insertFirst(78); list.insertFirst(24); list.insertFirst(22); list.insertFirst(56); list.displayList(); list.deleteFirst(); list.displayList(); System.out.println("find:" + list.find(56)); System.out.println("find:" + list.find(33)); System.out.println("delete find:" + list.delete(99)); System.out.println("delete find:" + list.delete(24)); list.displayList(); System.out.println("---reverse----"); list.displayListReverse(); } }List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList$Link@17dfafd1 List (first-->last): the data is 22 the data is 78 the data is 33 ---reverse--- List (first-->last): the data is 33 the data is 78 the data is 22
Single linked list: tail insertion method, back in first out - If the left end of the linked list is fixed, the linked list continues to extend to the right, this method of establishing a linked list is called tail insertion method.
When creating a linked list with tail insertion method, the head pointer is fixed, so a tail pointer must be set up to extend to the right of the linked list.
The first thing that comes from the tail insertion method is the head node.
public class SingleLinkedList2<T> { private Link<T> head; //The first node public SingleLinkedList2() { } public boolean isEmpty() { return head == null; } public void insertLast(T data) {//Insert Link<T> newLink = new Link<T>(data); if (head != null) { Link<T> nextP = head.next; if (nextP == null) { head.next = newLink; } else { Link<T> rear = null; while (nextP != null) { rear = nextP; nextP = nextP.next; } rear.next = newLink; } } else { head = newLink; } } public Link<T> deleteLast() {//Delete the tail of the chain Link<T> p = head; Link<T> q = head; while (p.next != null) {//The next node of p is not empty, q is equal to the current p (that is, q is the previous one and p is the next one). When the loop ends, q is equal to the penultimate end of the chain q = p; p = p.next; } //delete q.next = null; return p; } public Link<T> find(T t) { Link<T> find = head; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link<T> delete(T t) { if (isEmpty()) { return null; } else { if (head.data.equals(t)) { Link<T> temp = head; head = head.next; //Change the first node to return temp; } } Link<T> p = head; Link<T> q = head; while (!p.data.equals(t)) { if (p.next == null) {// means that return null has not been found at the end of the chain; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//Travel System.out.println("List (head-->last):"); Link<T> current = head; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//Inverse traversal Link<T> p = head, q = head.next, t; while (q != null) {//The pointer is reversed, and the traversed data order is backward t = q.next; //no3 if (p == head) {// When it is the original header, the .next of the head should be empty p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //In the if in the loop above, head.next is empty, When q is null and does not execute the loop, p is the original most data item. After inversion, p is assigned to head head = p; displayList(); } class Link<T> {//link point T data; //Data domain Link<T> next; //Successive pointer, node chain domain Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>(); list.insertLast(33); list.insertLast(78); list.insertLast(24); list.insertLast(22); list.insertLast(56); list.displayList(); list.deleteLast(); list.displayList(); System.out.println("find:" + list.find(56)); System.out.println("find:" + list.find(33)); System.out.println("delete find:" + list.delete(99)); System.out.println("delete find:" + list.delete(78)); list.displayList(); System.out.println("----reverse-----"); list.displayListReverse(); } }List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList2$Link@17dfafd1 List (head-->last): the data is 33 the data is 24 the data is 22 ---reverse--- List (head-->last): the data is 22 the data is 24 the data is 33
Simulate a double-ended linked list to implement stack and queues with linked lists
Double-ended linked list:
The double-ended linked list is very similar to the traditional linked list. It only has a new attribute added - that is, a reference to the last link is rear.
In this way, inserting at the end of the chain will become very easy. Just change the next of the rear to the newly added node, without looping to search for the last node, so there is insertFirst and insertLast
When deleting the chain header, you only need to change the reference point; when deleting the chain tail, you need to empty the next node of the penultimate node.
No reference points to it, so a loop is needed to read the operation
/** * Double-ended linked list* @author stone */ public class TwoEndpointList<T> { private Link<T> head; // first node private Link<T> rear; // tail pointer public TwoEndpointList() { } public T peekHead() { if (head != null) { return head.data; } return null; } public boolean isEmpty() { return head == null; } public void insertFirst(T data) {// Insert to the head of the chain Link<T> newLink = new Link<T>(data); newLink.next = head; //The next of the new node points to the previous node head = newLink; } public void insertLast(T data) {//Insert Link<T> newLink = new Link<T>(data); if (head == null) { rear = null; } if (rear != null) { rear.next = newLink; } else { head = newLink; head.next = rear; } rear = newLink; //The next time you insert, insert from the rear} public T deleteHead() {//Delete the chain header if (isEmpty()) return null; Link<T> temp = head; head = head.next; //Change the first node to be the next node if (head == null) { <span style="white-space:pre"> </span>rear = head; } return temp.data; } public T find(T t) { if (isEmpty()) { return null; } Link<T> find = head; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } if (find == null) { return null; } return find.data; } public T delete(T t) { if (isEmpty()) { return null; } else { if (head.data.equals(t)) { Link<T> temp = head; head = head.next; //Change the first node to the next node return temp.data; } } Link<T> p = head; Link<T> q = head; while (!p.data.equals(t)) { if (p.next == null) {//Indicate that return null has not been found at the end of the chain; } else { q = p; p = p.next; } } q.next = p.next; return p.data; } public void displayList() {//Travel System.out.println("List (head-->last):"); Link<T> current = head; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//Inverse traversal if (isEmpty()) { return; } Link<T> p = head, q = head.next, t; while (q != null) {//The pointer is reversed, and the traversed data order is backward t = q.next; //no3 if (p == head) {// When it is the original head, the .next of the head should be empty p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //In the if in the loop above, head.next is empty, and when q is null and does not execute the loop, p is the original most data item. After inversion, p is assigned to head head = p; displayList(); } class Link<T> {//link node T data; //Data domain Link<T> next; //Successive pointer, node chain domain Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { TwoEndpointList<Integer> list = new TwoEndpointList<Integer>(); list.insertLast(1); list.insertFirst(2); list.insertLast(3); list.insertFirst(4); list.insertLast(5); list.displayList(); list.deleteHead(); list.displayList(); System.out.println("find:" + list.find(6)); System.out.println("find:" + list.find(3)); System.out.println("delete find:" + list.delete(6)); System.out.println("delete find:" + list.delete(5)); list.displayList(); System.out.println("---reverse----"); list.displayListReverse(); } }List (head-->last): the data is 4 the data is 2 the data is 1 the data is 3 the data is 5 List (head-->last): the data is 2 the data is 1 the data is 3 the data is 5 find:null find:3 delete find:null delete find:5 List (head-->last): the data is 2 the data is 1 the data is 3 ---reverse--- List (head-->last): the data is 3 the data is 1 the data is 2
Use linked lists to implement the stack, and use the single linked list before inserting it.
This class uses a double-ended linked list to implement:
public class LinkStack<T> { private TwoEndpointList<T> datas; public LinkStack() { datas = new TwoEndpointList<T>(); } // Put into the stack public void push(T data) { datas.insertFirst(data); } // Put out the stack public T pop() { return datas.deleteHead(); } // Check the top of the stack public T peek() { return datas.peekHead(); } // Whether the stack is empty public boolean isEmpty() { return datas.isEmpty(); } public static void main(String[] args) { LinkStack<Integer> stack = new LinkStack<Integer>(); for (int i = 0; i < 5; i++) { stack.push(i); } for (int i = 0; i < 5; i++) { Integer peek = stack.peek(); System.out.println("peek:" + peek); } for (int i = 0; i < 6; i++) { Integer pop = stack.pop(); System.out.println("pop:" + pop); } System.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); } for (int i = 5; i > 0; i--) { Integer peek = stack.peek(); System.out.println("peek:" + peek); } for (int i = 5; i > 0; i--) { Integer pop = stack.pop(); System.out.println("pop:" + pop); } } }peek:4 peek:4 peek:4 peek:4 peek:4 peek:4 pop:4 pop:3 pop:2 pop:1 pop:1 pop:0 pop:null --- peek:1 peek:1 peek:1 peek:1 pop:1 pop:1 pop:2 pop:3 pop:4 pop:5
The linked list implementation queue is implemented using a double-ended linked list:
public class LinkQueue<T> { private TwoEndpointList<T> list; public LinkQueue() { list = new TwoEndpointList<T>(); } //Insert the tail of the queue public void insert(T data) { list.insertLast(data); } //Remove the head of the team public T remove() { return list.deleteHead(); } //View the head of the team public T peek() { return list.peekHead(); } public boolean isEmpty() { return list.isEmpty(); } public static void main(String[] args) { LinkQueue<Integer> queue = new LinkQueue<Integer>(); for (int i = 1; i < 5; i++) { queue.insert(i); } for (int i = 1; i < 5; i++) { Integer peek = queue.peek(); System.out.println("peek:" + peek); } for (int i = 1; i < 5; i++) { Integer remove = queue.remove(); System.out.println("remove:" + remove); } System.out.println("----"); for (int i = 5; i > 0; i--) { queue.insert(i); } for (int i = 5; i > 0; i--) { Integer peek = queue.peek(); System.out.println("peek2:" + peek); } for (int i = 5; i > 0; i--) { Integer remove = queue.remove(); System.out.println("remove:" + remove); } } }peek:1 peek:1 peek:1 peek:1 peek:1 remove:1 remove:2 remove:3 remove:4 --- peek2:5 peek2:5 peek2:5 peek2:5 peek2:5 remove:5 remove:4 remove:3 remove:2 remove:1