On m'a récemment posé des questions sur les listes chaînées alors qu'un ami et moi parlions de Java. Pour être honnête, j’ai très peu appris en près d’un an que j’apprends la programmation. J'ai appris Java et C# en tant que langages, et j'ai appris un peu de javascript Html CSS sur le Web. En raison de ma préférence, je suis plus sérieux lors de l'apprentissage de WinForm et je fais également des recherches sur les opérations de base de données. Mais je n'ai jamais étudié ou recherché des listes chaînées. De plus, j'ai lu WPF récemment et le cours a également atteint JSP, ce qui est relativement serré.
Mais j'ai quand même mis une nuit et une demi-journée à regarder la liste chaînée à sens unique. Et j'ai essayé d'écrire un exemple en utilisant Java. Les amis qui n'ont jamais été exposés à des listes chaînées peuvent l'utiliser comme référence. J'espère que vous pourrez fournir des opinions plus précieuses.
Expliquons d’abord ce qu’est une liste chaînée. Autant que je sache, une liste chaînée est une structure de données, au même niveau qu'un tableau. Par exemple, l'ArrayList que nous utilisons en Java est implémentée sur la base d'un tableau. Le principe de mise en œuvre de LinkedList est la liste chaînée. Mon professeur a dit que les listes chaînées ne sont pas efficaces lors du parcours de boucles, mais qu'elles présentent des avantages évidents lors de l'insertion et de la suppression. Ensuite, il a plus de dix ans d’expérience en programmation, j’y crois. Mais je ne sais pas s’il parle de listes doublement chaînées. Ici, nous n’avons qu’une compréhension des listes chaînées unidirectionnelles.
Les listes chaînées (les listes chaînées mentionnées dans cet article sont toutes des listes chaînées unidirectionnelles, ci-après appelées listes chaînées unidirectionnelles) sont en fait composées de nœuds (Node), et une liste chaînée a une durée indéfinie nombre de nœuds. Il n'y a qu'un seul nœud principal (Head) exposé à l'extérieur. Toutes nos opérations sur la liste chaînée sont effectuées directement ou indirectement via son nœud principal.
Le nœud est composé d'un objet qui doit être stocké et d'une référence au nœud suivant. En d’autres termes, le nœud comporte deux membres : l’objet stocké et la référence au nœud suivant.
Peut-être que vous ne le comprenez pas de cette façon, alors je posterai une photo et ce sera peut-être plus facile pour vous de comprendre.
Le code clé pour implémenter les opérations de base de la liste chaînée unique Java est le suivant :
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);
}
}Ce qui précède est la liste chaînée unique Java introduite par l'éditeur. La mise en œuvre des opérations de base, j'espère que cela sera utile à tout le monde. Si vous avez des questions, laissez-moi un message et l'éditeur vous répondra à temps. Je voudrais également vous remercier tous pour votre soutien au site Web PHP chinois !
Pour plus d'articles liés à la mise en œuvre des opérations de base de la liste Java à lien unique, veuillez faire attention au site Web PHP chinois !