Simulation einer einfach verknüpften Liste
Lineare Tabelle:
Eine lineare Tabelle (auch Sequenztabelle genannt) ist die grundlegendste, einfachste und am häufigsten verwendete Datenstruktur.
Die Beziehung zwischen Datenelementen in einer linearen Tabelle ist eine Eins-zu-Eins-Beziehung, das heißt, mit Ausnahme des ersten und letzten Datenelements sind andere Datenelemente Ende an Ende verbunden.
Der lineare Tisch hat eine einfache logische Struktur und ist einfach zu implementieren und zu bedienen.
In praktischen Anwendungen werden lineare Tabellen in Form spezieller linearer Tabellen wie Stapel, Warteschlangen und Zeichenfolgen verwendet.
Die grundlegenden Merkmale der linearen Struktur sind:
1. Es darf nur ein „erstes Element“ in der Menge geben;
2. Es darf nur ein „letztes Element“ im Satz vorhanden sein; Bis auf das letzte Element haben alle Elemente einen eindeutigen Nachfolger (Konsequenz);
4. Mit Ausnahme des ersten Elements haben alle Elemente einen eindeutigen Vorläufer (Antezedens).
Eine verknüpfte Liste ist eine nicht kontinuierliche und nicht sequentielle Speicherstruktur auf einer physischen Speichereinheit. Die logische Reihenfolge der Datenelemente wird durch die Verknüpfungsreihenfolge der Zeiger in der realisiert verknüpfte Liste
Jedes Datenelement ist in „Links“ enthalten.
Der Linkpunkt ist ein Objekt einer Klasse, die Link genannt werden kann. Es gibt viele ähnliche Linkpunkte in der verknüpften Liste, und jeder Link enthält ein Feld „Next“, das auf den nächsten Linkpunkt verweist.
Das verknüpfte Listenobjekt selbst speichert zunächst eine Referenz, die auf den ersten Verknüpfungspunkt zeigt. (Wenn es kein erstes gibt, kann es nicht positioniert werden)
Die verknüpfte Liste kann nicht direkt auf Datenelemente wie das Array zugreifen (unter Verwendung von Indizes), sondern muss die Beziehung zwischen den Daten verwenden, um das nächste zu lokalisieren, dh auf das nächste zuzugreifen Link, auf den durch den Link-Punkt verwiesen wird Klicken Sie und dann den nächsten, bis auf die erforderlichen Daten zugegriffen wird
Die zeitliche Komplexität des Einfügens und Löschens am Anfang der Kette beträgt O(1), da Sie nur den Zeiger ändern müssen Suchen und löschen Sie den angegebenen Ergebnispunkt der Referenz und fügen Sie ihn nach dem angegebenen Knoten ein. Diese Operationen erfordern im Durchschnitt das Durchsuchen der Hälfte der Knoten in der verknüpften Liste und die Effizienz beträgt O (N).
Einfach verknüpfte Liste:
Die Darstellung einer linearen Liste als „Knotenfolge“ wird als linear verknüpfte Liste (einfach verknüpfte Liste) bezeichnet.
Es handelt sich um eine verkettete Zugriffsdatenstruktur, die in einer Reihe von gespeichert ist Speichereinheiten mit beliebigen Adressen. (Diese Gruppe von Speichereinheiten kann entweder kontinuierlich oder diskontinuierlich sein)
Die Struktur des Verbindungspunkts:
Die Datenfelddaten, die den Knotenwert speichern;Der Zeiger Feld (Kettenfeld), das die Referenz des nächsten Knotens speichert
Eine verknüpfte Liste mit nur einem Linkfeld für jeden Knoten wird als einfach verknüpfte Liste bezeichnet. In einer Richtung gibt es nur Verweise auf nachfolgende Knoten
/**
* 单链表:头插法 后进先出
* 将链表的左边称为链头，右边称为链尾。
* 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。
* 头插法最先得到的是尾结点
* @author stone
*/
public class SingleLinkedList<T> {
private Link<T> first; //首结点
public SingleLinkedList() {
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(T data) {// 插入 到 链头
Link<T> newLink = new Link<T>(data);
newLink.next = first; //新结点的next指向上一结点
first = newLink;
}
public Link<T> deleteFirst() {//删除 链头
Link<T> temp = first;
first = first.next; //变更首结点，为下一结点
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; //变更首结点，为下一结点
return temp;
}
}
Link<T> p = first;
Link<T> q = first;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍历
System.out.println("List (first-->last):");
Link<T> current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
Link<T> p = first, q = first.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == first) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把first.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给first
first = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
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
Einfach verknüpfte Liste: Schwanzeinfügungsmethode, Last In First Out – Wenn das linke Ende der verknüpften Liste festgelegt ist, wird die verknüpfte Liste weiterhin nach rechts erweitert Die Erstellung einer verknüpften Liste wird als Tail-Insertion-Methode bezeichnet.
Wenn die Tail-Insert-Methode eine verknüpfte Liste erstellt, ist der Kopfzeiger festgelegt, sodass ein Tail-Zeiger so eingerichtet werden muss, dass er sich auf die rechte Seite der verknüpften Liste erstreckt.Das erste, was durch die Tail-Insert-Methode erhalten wird ist der Kopfknoten.
public class SingleLinkedList2<T> {
private Link<T> head; //首结点
public SingleLinkedList2() {
}
public boolean isEmpty() {
return head == null;
}
public void insertLast(T data) {//在链尾 插入
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() {//删除 链尾
Link<T> p = head;
Link<T> q = head;
while (p.next != null) {// p的下一个结点不为空，q等于当前的p(即q是上一个，p是下一个) 循环结束时，q等于链尾倒数第二个
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; //变更首结点，为下一结点
return temp;
}
}
Link<T> p = head;
Link<T> q = head;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍历
System.out.println("List (head-->last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
Link<T> p = head, q = head.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == head) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
head = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
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
Simulieren Sie eine doppelendige verknüpfte Liste zu einer verknüpften Liste Stapel und Warteschlange implementieren
Doppelend verknüpfte Liste:Doppelend verknüpfte Liste ist der herkömmlichen verknüpften Liste sehr ähnlich. Sie fügt lediglich ein neues Attribut hinzu – den Verweis auf den letzten Verknüpfungspunkt hinten
Auf diese Weise ändert sich das Einfügen am Ende der Kette. Es ist sehr einfach, den nächsten Knoten auf den neuen Knoten umzustellen. Es ist nicht erforderlich, die Suche bis zum letzten Knoten zu durchlaufen. Daher müssen Sie beim Löschen des Verbindungskopfes mit insertFirst und insertLast nur den Referenzpunkt ändern. Ja; beim Löschen des Endes der Kette müssen Sie den nächsten Knoten des vorletzten Knotens leer machen,
und es gibt keinen Verweis darauf, daher müssen Sie immer noch eine Schleife durchlaufen, um die Operation
/**
* 双端链表
* @author stone
*/
public class TwoEndpointList<T> {
private Link<T> head; //首结点
private Link<T> rear; //尾部指针
public TwoEndpointList() {
}
public T peekHead() {
if (head != null) {
return head.data;
}
return null;
}
public boolean isEmpty() {
return head == null;
}
public void insertFirst(T data) {// 插入 到 链头
Link<T> newLink = new Link<T>(data);
newLink.next = head; //新结点的next指向上一结点
head = newLink;
}
public void insertLast(T data) {//在链尾 插入
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; //下次插入时，从rear处插入
}
public T deleteHead() {//删除 链头
if (isEmpty()) return null;
Link<T> temp = head;
head = head.next; //变更首结点，为下一结点
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; //变更首结点，为下一结点
return temp.data;
}
}
Link<T> p = head;
Link<T> q = head;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p.data;
}
public void displayList() {//遍历
System.out.println("List (head-->last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
if (isEmpty()) {
return;
}
Link<T> p = head, q = head.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == head) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
head = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
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
public class LinkStack<T> {
private TwoEndpointList<T> datas;
public LinkStack() {
datas = new TwoEndpointList<T>();
}
// 入栈
public void push(T data) {
datas.insertFirst(data);
}
// 出栈
public T pop() {
return datas.deleteHead();
}
// 查看栈顶
public T peek() {
return datas.peekHead();
}
//栈是否为空
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);
}
}
}Implementierungswarteschlange für verknüpfte Listen Mit doppelendiger verknüpfter Liste implementiert:
Für verwandte Artikel, in denen Beispiele für verknüpfte Listendatenstrukturen erläutert werden, beachten Sie bitte die chinesische PHP-Website!peek:4 peek:4 peek:4 peek:4 peek:4 pop:4 pop:3 pop:2 pop:1 pop:0 pop:null ---- peek:1 peek:1 peek:1 peek:1 peek:1 pop:1 pop:2 pop:3 pop:4 pop:5
