笔记大全

java怎么实现双向链表的增删改

更新时间：2023-10-06

双向链表的概念

双向链表是一种常见的数据结构，它由节点组成，每个节点包含一个数据元素和两个指针，分别指向前一个节点和后一个节点。与单向链表不同，双向链表可以在任意位置快速插入和删除节点，因为它可以从前向后或从后向前遍历。

双向链表的实现

为了实现双向链表，我们首先定义一个包含数据和指针的节点类。代码如下：

class Node {
    int data;
    Node prev;
    Node next;
    
    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

然后，我们创建一个名为LinkedList的双向链表类，其中包含添加（add）、删除（remove）和修改（update）等操作的实现。

class LinkedList {
    Node head;
    
    public LinkedList() {
        this.head = null;
    }
    
    // 在链表末尾添加节点
    public void add(int data) {
        Node newNode = new Node(data);
        
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
        }
    }
    
    // 删除指定位置的节点
    public void remove(int position) {
        if (position < 0 || head == null) {
            return;
        }
        
        if (position == 0) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
        } else {
            Node current = head;
            int count = 0;
            
            while (count < position && current.next != null) {
                current = current.next;
                count++;
            }
            
            if (count == position) {
                current.prev.next = current.next;
                if (current.next != null) {
                    current.next.prev = current.prev;
                }
            }
        }
    }
    
    // 修改指定位置的节点的值
    public void update(int position, int newData) {
        if (position < 0 || head == null) {
            return;
        }
        
        Node current = head;
        int count = 0;
        
        while (count < position && current.next != null) {
            current = current.next;
            count++;
        }
        
        if (count == position) {
            current.data = newData;
        }
    }
}

双向链表的增删改

上述代码展示了如何实现双向链表的添加、删除和修改操作。下面分别介绍这三种操作的具体实现。

1. 添加操作

在双向链表的末尾添加节点是一种常见的操作。首先判断链表是否为空，如果为空，则直接将新节点设置为头节点。如果链表不为空，则遍历链表直到找到最后一个节点，将新节点添加到其后面，同时将新节点的前驱指针指向当前最后节点。

public void add(int data) {
    Node newNode = new Node(data);
    
    if (head == null) {
        head = newNode;
    } else {
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.prev = current;
    }
}

2. 删除操作

双向链表的删除操作需要考虑删除节点的位置。如果要删除的位置是链表的头节点，我们只需要将头指针指向下一个节点，并将下一个节点的前驱指针设置为空。否则，我们需要遍历链表，找到要删除的位置，并将要删除节点的前驱指针的next指向要删除节点的next，同时将要删除节点的下一个节点的前驱指针指向要删除节点的前驱指针。

public void remove(int position) {
    if (position < 0 || head == null) {
        return;
    }
    
    if (position == 0) {
        head = head.next;
        if (head != null) {
            head.prev = null;
        }
    } else {
        Node current = head;
        int count = 0;
        
        while (count < position && current.next != null) {
            current = current.next;
            count++;
        }
        
        if (count == position) {
            current.prev.next = current.next;
            if (current.next != null) {
                current.next.prev = current.prev;
            }
        }
    }
}

3. 修改操作

双向链表的修改操作是通过遍历链表找到指定位置的节点，然后将其数据值修改为新的值。

public void update(int position, int newData) {
    if (position < 0 || head == null) {
        return;
    }
    
    Node current = head;
    int count = 0;
    
    while (count < position && current.next != null) {
        current = current.next;
        count++;
    }
    
    if (count == position) {
        current.data = newData;
    }
}

总结

通过使用Java语言，可以实现双向链表的增删改操作。在双向链表中，我们可以方便地在任意位置添加、删除和修改节点，它比单向链表更具灵活性。在实现双向链表时，我们需要定义节点类和链表类，并在链表类中编写相应的添加、删除和修改操作的代码。

在添加操作中，我们需要首先判断链表是否为空，然后将新节点添加到链表的末尾。删除操作需要判断删除位置是否合法，然后找到要删除的节点并修改指针。修改操作通过遍历链表找到指定位置的节点，然后将其数据值修改为新的值。以上操作结合起来，可以实现双向链表的增删改。

c语言编程笔录