So implementieren Sie grundlegende Operationen (Hinzufügen, Löschen, Überprüfen, Ändern) in verknüpften Java-Listen

Eine verknüpfte Liste ist ebenfalls eine lineare Datenstruktur. Im Gegensatz zu einem Array wird eine verknüpfte Liste zufällig im Speicher gespeichert.

Das Folgende ist ein vollständiges Beispiel, das die vier Vorgänge einer verknüpften Liste abdeckt. Es sind einige Punkte zu beachten:

(1) Vor dem Hinzufügen, Löschen, Ändern oder Überprüfen müssen Sie Folgendes tun Überprüfen Sie die folgende Markierung auf Grenzbeurteilung.

(2) Das Hinzufügen eines Knotens mit dem Namen „letzter“ kann Operationen am Ende der verknüpften Liste erleichtern und den Zeitaufwand für die Suche nach dem letzten Knoten verringern. 3) Beim Einfügen eines Elements in die verknüpfte Liste suchen wir zuerst den prevNode des vorherigen einzufügenden Knotens und zeichnen dann den nächsten prevNode auf. Beim Einfügen zeigen wir zuerst den nächsten prevNode auf den einzufügenden Knoten und dann Der nächste einzufügende Knoten zeigt auf den aktuellen nächsten. Dies unterscheidet sich auch geringfügig von der Operation in C++

(4) Verwenden Sie beim Löschen eines Knotens „removedNode“, um den Rückgabewert des gelöschten Knotens aufzuzeichnen, und vergessen Sie nicht, die Größe um 1 zu reduzieren.

Empfohlene kostenlose Video-Tutorials:

kostenlose Java-Video-Tutorials

Die Bedienungsbeispiele lauten wie folgt:

public class MyLinkedList {
    //定义一个静态的内部类
    private static class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
 
    private Node head;
    private Node last;//为了方便尾部插入元素的操作
    private int size;//size表示链表的实际长度
 
    public void insert(int data, int index)throws Exception{
        if(index < 0 || index > size)
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        Node insertedNode = new Node(data);
        if(size == 0){//插入第一个元素时元素个数为0
            head = insertedNode;
            last = insertedNode;
        }else if(size == index){//在链表的末尾插入
            last.next = insertedNode;
            last = insertedNode;
        }else{
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.next;
            prevNode.next = insertedNode;
            insertedNode.next = nextNode;
        }
        size++;
    }
 
    public void update(int data, int index) throws Exception{
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        if(index == 0)
            head.data = data;
        else if(index == size - 1)
            last.data = data;
        else{
            Node temp = get(index);
            temp.data = data;
        }
    }
 
    public Node remove(int index) throws Exception {
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node removedNode = null;//不给removedNode分配堆内存
        if(index == 0){
            removedNode = head;
            head = head.next;
        }
        else if(index == size - 1){
            //删除尾结点
            Node prevNode = get(index - 1);
            removedNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        }
        else{
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode;
        }
        size--;
        return removedNode;
    }
 
 
 
    //查找链表元素
    public Node get(int index) throws Exception{
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node temp = head;
        for(int i = 0; i < index; i++){
            temp = temp.next;
        }
//        size--;
        return temp;
    }
 
    //输出链表
    public void output(){
        Node temp = head;
        while(temp != null){
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
 
    public static void main(String[] args) throws Exception{
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.insert(3,0);
        myLinkedList.insert(7,1);
        myLinkedList.insert(9,2);
        myLinkedList.insert(5,3);
        myLinkedList.insert(6,1);
        myLinkedList.remove(0);
        myLinkedList.update(2,1);
        myLinkedList.output();
        System.out.println(myLinkedList.size);
    }
}

Wenn Sie weitere verwandte Tutorials erfahren möchten, Sie können besuchen:

Einführung in die Java-Entwicklung

Das obige ist der detaillierte Inhalt vonSo implementieren Sie grundlegende Operationen (Hinzufügen, Löschen, Überprüfen, Ändern) in verknüpften Java-Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!