笔记大全

java数据结构单向链表的操作有哪些

更新时间：2023-10-06

前言：

单向链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的引用。单向链表的特点是数据元素之间通过节点的引用关联起来，形成一个有序的链表。在Java中，通过定义节点类和链表类，可以方便地实现对单向链表的操作。

1. 创建链表

要创建一个单向链表，首先需要定义一个节点类（Node）和一个链表类（LinkedList）。节点类包含一个数据元素和一个指向下一个节点的引用，链表类包含一个头节点的引用和一些基本的操作方法。创建链表的步骤如下： 1) 定义一个节点类Node，包含一个数据元素和一个指向下一个节点的引用。 2) 定义一个链表类LinkedList，包含一个头节点的引用。 3) 在链表类中定义一个方法add，用于向链表中添加节点。 4) 在main方法中，创建链表对象，并调用add方法向链表中添加节点。示例代码如下：

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

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

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
    }
}

2. 在链表头部插入节点

在链表头部插入一个节点是一种常见的操作，可以通过将新节点的next指向原先的头节点，然后更新头节点的引用来实现。插入节点的步骤如下： 1) 创建一个新节点newNode，并设置新节点的数据元素。 2) 将新节点的next指向原先的头节点。 3) 更新链表的头节点的引用，将其指向新节点。示例代码如下：

public class LinkedList {
    Node head;
    
    // 其他方法...
    
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtBeginning(4);
        list.insertAtBeginning(5);
    }
}

3. 在链表尾部插入节点

在链表尾部插入一个节点也是一种常见的操作，可以通过遍历链表找到最后一个节点，然后将其next指向新节点来实现。插入节点的步骤如下： 1) 创建一个新节点newNode，并设置新节点的数据元素。 2) 如果链表为空，则将头节点直接指向新节点。 3) 否则，从头节点开始遍历链表，直到找到最后一个节点。 4) 将最后一个节点的next指向新节点。示例代码如下：

public class LinkedList {
    Node head;
    
    // 其他方法...
    
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node currentNode = head;
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            currentNode.next = newNode;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtEnd(6);
        list.insertAtEnd(7);
    }
}

4. 删除链表中的节点

删除链表中的节点可以根据节点的值或位置进行。根据节点的值删除节点的步骤如下： 1) 如果链表为空，则没有节点可以删除。 2) 如果要删除的节点是头节点，则将头节点的next作为新的头节点。 3) 否则，从头节点开始遍历链表，找到要删除的节点的前一个节点。 4) 更新前一个节点的next，将其指向要删除节点的下一个节点。示例代码如下：

public class LinkedList {
    Node head;
    
    // 其他方法...
    
    public void deleteByValue(int data) {
        if (head == null) {
            return;
        }
        if (head.data == data) {
            head = head.next;
        } else {
            Node currentNode = head;
            while (currentNode.next != null && currentNode.next.data != data) {
                currentNode = currentNode.next;
            }
            if (currentNode.next != null) {
                currentNode.next = currentNode.next.next;
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.deleteByValue(5);
    }
}

总结：本文介绍了单向链表的创建、在链表头部插入节点、在链表尾部插入节点、删除链表中的节点等常见操作。通过定义节点类和链表类，可以方便地实现对链表的操作。在实际应用中，单向链表可以作为数据结构的一种选择，用于存储和处理具有动态性质的数据。对于大规模数据集合的查找、插入和删除等操作，链表相比数组具有更好的性能。因此，掌握链表的基本操作对于理解和使用数据结构具有重要意义。

c语言编程笔录