Qu'est-ce qu'une liste chaînée en Java

LinkedList utilise une structure de données de liste circulaire doublement chaînée. Par rapport à ArrayList basé sur un tableau, il s'agit de deux technologies d'implémentation complètement différentes, ce qui détermine également qu'elles seront adaptées à des scénarios de travail complètement différents.

La liste chaînée est une structure de données de base commune, une table linéaire, mais elle ne stocke pas les données dans un ordre linéaire, mais dans chaque Un pointeur vers le nœud suivant est stocké dans un nœud.

L'utilisation de la structure de liste chaînée peut surmonter l'inconvénient de la liste chaînée de tableau selon laquelle la taille des données doit être connue à l'avance. La structure de liste chaînée peut utiliser pleinement l'espace mémoire de l'ordinateur et réaliser une gestion dynamique flexible de la mémoire. Cependant, la liste chaînée perd l'avantage de la lecture aléatoire du tableau, et en même temps, la surcharge spatiale de la liste chaînée est relativement importante en raison de l'augmentation du champ de pointeur du nœud.

Exemple :

package com.ys.link;

public class DoublePointLinkedList {
    private Node head;//头节点
    private Node tail;//尾节点
    private int size;//节点的个数
    
    private class Node{
        private Object data;
        private Node next;
        
        public Node(Object data){
            this.data = data;
        }
    }
    
    public DoublePointLinkedList(){
        size = 0;
        head = null;
        tail = null;
    }
    
    //链表头新增节点
    public void addHead(Object data){
        Node node = new Node(data);
        if(size == 0){//如果链表为空，那么头节点和尾节点都是该新增节点
            head = node;
            tail = node;
            size++;
        }else{
            node.next = head;
            head = node;
            size++;
        }
    }
    
    //链表尾新增节点
    public void addTail(Object data){
        Node node = new Node(data);
        if(size == 0){//如果链表为空，那么头节点和尾节点都是该新增节点
            head = node;
            tail = node;
            size++;
        }else{
            tail.next = node;
            tail = node;
            size++;
        }
    }
    
    //删除头部节点，成功返回true，失败返回false
    public boolean deleteHead(){
        if(size == 0){//当前链表节点数为0
            return false;
        }
        if(head.next == null){//当前链表节点数为1
            head = null;
            tail = null;
        }else{
            head = head.next;
        }
        size--;
        return true;
    }
    //判断是否为空
    public boolean isEmpty(){
        return (size ==0);
    }
    //获得链表的节点个数
    public int getSize(){
        return size;
    }
    
    //显示节点信息
    public void display(){
        if(size >0){
            Node node = head;
            int tempSize = size;
            if(tempSize == 1){//当前链表只有一个节点
                System.out.println("["+node.data+"]");
                return;
            }
            while(tempSize>0){
                if(node.equals(head)){
                    System.out.print("["+node.data+"->");
                }else if(node.next == null){
                    System.out.print(node.data+"]");
                }else{
                    System.out.print(node.data+"->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        }else{//如果链表一个节点都没有，直接打印[]
            System.out.println("[]");
        }
    }

}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!