Ich wurde kürzlich nach verknüpften Listen gefragt, als ein Freund und ich über Java diskutierten. Ehrlich gesagt habe ich in dem fast einem Jahr, in dem ich Programmieren gelernt habe, sehr wenig gelernt. Ich habe Java und C# als Sprachen gelernt und etwas über HTML+CSS+Javascript im Web gelernt. Aufgrund meiner Vorliebe lerne ich WinForm ernsthafter und recherchiere auch etwas über Datenbankoperationen. Aber ich habe nie verknüpfte Listen studiert oder recherchiert. Außerdem habe ich kürzlich WPF studiert und der Kurs hat auch JSP erreicht, was relativ eng ist.
Aber ich habe trotzdem eine Nacht und einen halben Tag gebraucht, um mir die einseitig verknüpfte Liste anzusehen. Und ich habe versucht, ein Beispiel mit Java zu schreiben. Freunde, die noch nie mit verlinkten Listen in Kontakt gekommen sind, können diese als Referenz verwenden. Ich hoffe, Sie können weitere wertvolle Meinungen abgeben.
Erklären wir zunächst, was eine verknüpfte Liste ist. Soweit ich weiß, ist eine verknüpfte Liste eine Datenstruktur auf derselben Ebene wie ein Array. Beispielsweise wird die ArrayList, die wir in Java verwenden, basierend auf einem Array implementiert. Das Implementierungsprinzip von LinkedList ist eine verknüpfte Liste. Mein Lehrer sagte, dass verknüpfte Listen beim Durchlaufen von Schleifen nicht effizient seien, beim Einfügen und Löschen jedoch offensichtliche Vorteile hätten. Dann hat er, glaube ich, mehr als zehn Jahre Programmiererfahrung. Aber ich weiß nicht, ob er von doppelt verknüpften Listen spricht. Hier verstehen wir nur einseitig verknüpfte Listen.
Verknüpfte Listen (die in diesem Artikel erwähnten verknüpften Listen sind alle einseitig verknüpfte Listen, im Folgenden als einseitig verknüpfte Listen bezeichnet) bestehen tatsächlich aus Knoten (Knoten), und eine verknüpfte Liste hat eine Unbestimmtheit Anzahl der Knoten. Es gibt nur einen Kopfknoten (Head), der nach außen sichtbar ist. Alle unsere Operationen an der verknüpften Liste werden direkt oder indirekt über seinen Kopfknoten ausgeführt.
Knoten besteht aus einem Objekt, das gespeichert werden muss, und einem Verweis auf den nächsten Knoten. Mit anderen Worten: Der Knoten hat zwei Mitglieder: das gespeicherte Objekt und die Referenz auf den nächsten Knoten.
Vielleicht verstehst du es nicht so, also poste ich ein Bild und es könnte für dich einfacher zu verstehen sein.
Der Schlüsselcode zum Implementieren der Grundoperationen der einfach verknüpften Java-Liste lautet wie folgt:
package com.tyxh.link;
//节点类
public class Node {
protected Node next; //指针域
protected int data;//数据域
public Node( int data) {
this. data = data;
}
//显示此节点
public void display() {
System. out.print( data + " ");
}
}
package com.tyxh.link;
//单链表
public class LinkList {
public Node first; // 定义一个头结点
private int pos = 0;// 节点的位置
public LinkList() {
this. first = null;
}
// 插入一个头节点
public void addFirstNode( int data) {
Node node = new Node(data);
node. next = first;
first = node;
}
// 删除一个头结点,并返回头结点
public Node deleteFirstNode() {
Node tempNode = first;
first = tempNode. next;
return tempNode;
}
// 在任意位置插入节点 在index的后面插入
public void add(int index, int data) {
Node node = new Node(data);
Node current = first;
Node previous = first;
while ( pos != index) {
previous = current;
current = current. next;
pos++;
}
node. next = current;
previous. next = node;
pos = 0;
}
// 删除任意位置的节点
public Node deleteByPos( int index) {
Node current = first;
Node previous = first;
while ( pos != index) {
pos++;
previous = current;
current = current. next;
}
if(current == first) {
first = first. next;
} else {
pos = 0;
previous. next = current. next;
}
return current;
}
// 根据节点的data删除节点(仅仅删除第一个)
public Node deleteByData( int data) {
Node current = first;
Node previous = first; //记住上一个节点
while (current. data != data) {
if (current. next == null) {
return null;
}
previous = current;
current = current. next;
}
if(current == first) {
first = first. next;
} else {
previous. next = current. next;
}
return current;
}
// 显示出所有的节点信息
public void displayAllNodes() {
Node current = first;
while (current != null) {
current.display();
current = current. next;
}
System. out.println();
}
// 根据位置查找节点信息
public Node findByPos( int index) {
Node current = first;
if ( pos != index) {
current = current. next;
pos++;
}
return current;
}
// 根据数据查找节点信息
public Node findByData( int data) {
Node current = first;
while (current. data != data) {
if (current. next == null)
return null;
current = current. next;
}
return current;
}
}
package com.tyxh.link;
//测试类
public class TestLinkList {
public static void main(String[] args) {
LinkList linkList = new LinkList();
linkList.addFirstNode(20);
linkList.addFirstNode(21);
linkList.addFirstNode(19);
//19,21,20
linkList.add(1, 22); //19,22,21,20
linkList.add(2, 23); //19,22,23,21,20
linkList.add(3, 99); //19,22,23,99,21,20
linkList.displayAllNodes();
// Node node = linkList.deleteFirstNode();
// System.out.println("node : " + node.data);
// linkList.displayAllNodes();
// node = linkList.deleteByPos(2);
// System.out.println("node : " + node.data);
// linkList.displayAllNodes();
// linkList.deleteFirstNode();
Node node = linkList.deleteByData(19);
// Node node = linkList.deleteByPos(0);
System. out.println( "node : " + node. data);
linkList.displayAllNodes();
Node node1 = linkList.findByPos(0);
System. out.println( "node1: " + node1. data);
Node node2 = linkList.findByData(22);
System. out.println( "node2: " + node2. data);
}
}Nach dem Login kopieren
Das Obige ist die Einführung der einfach verknüpften Java-Liste Ich hoffe, dass die Implementierung grundlegender Vorgänge für alle hilfreich ist. Wenn Sie Fragen haben, hinterlassen Sie mir bitte eine Nachricht. Der Herausgeber wird Ihnen rechtzeitig antworten. Ich möchte mich auch bei Ihnen allen für Ihre Unterstützung der chinesischen PHP-Website bedanken!
Weitere Artikel zur Implementierung grundlegender Operationen der einfach verknüpften Java-Liste finden Sie auf der chinesischen PHP-Website!
