【Java数据结构】链表(Linked List)-单向链表

浅浅的花香味﹌ 2023-09-30 23:19 10阅读 0赞

#### 一、什么是链表(Linked List) ####

链表(Linked List)是一种常见的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的引用。链表可以用于实现栈、队列等数据结构。相比数组，链表的优点在于可以高效地进行插入和删除操作，因为不需要移动大量元素。

**1、链表的概念**

链表由一系列节点（Node）组成，每个节点包含了一个数据元素和一个指向下一个节点的指针。链表的头节点（Head）指向第一个节点，尾节点（Tail）指向最后一个节点，最后一个节点指针指向null。

**链表可以分为单向链表、双向链表和循环链表等不同类型**。单向链表中每个节点只有一个指针指向下一个节点，而双向链表中每个节点有两个指针，分别指向上一个节点和下一个节点。循环链表的尾节点指针指向头节点，形成一个闭环。

**2、链表的实现**

链表的实现通常包括以下几个部分：

*  **定义节点类：**定义节点类包含数据元素和指向下一个节点的指针。
 *  **定义链表类：**定义链表类包含头节点和节点数量等属性，以及插入、删除、查找等方法。
 *  **实现节点插入：**新建节点并将其插入到链表中。
 *  **实现节点删除：**找到要删除的节点并将其从链表中删除。
 *  **实现节点查找：**遍历链表找到指定元素。

#### 二、实现一个单向链表 ####

Java中可以使用类来表示链表节点和链表，以下是一个基本的教程来实现一个**单向链表。**

**1、定义链表节点类**

链表节点类包含两个成员变量：节点值和指向下一个节点的引用。

class ListNode {
        int val;
        ListNode next;
        
        
        public ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

**2、实现链表类**

链表类包含两个成员变量：链表头指针和链表长度。其中，链表头指针指向第一个节点。

class LinkedList {
        ListNode head;
        int size;
    
        
        public LinkedList() {
            this.head = null;
            this.size = 0;
        }
    
       
        public void add(int val) {
            ListNode newNode = new ListNode(val);
    
            if (head == null) {
                head = newNode;
            } else {
                ListNode curr = head;
                while (curr.next != null) {
                    curr = curr.next;
                }
                curr.next = newNode;
            }
    
            size++;
        }
    
        
        public int get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException();
            }
    
            ListNode curr = head;
            for (int i = 0; i < index; i++) {
                curr = curr.next;
            }
    
            return curr.val;
        }
    }

**3、测试链表类**

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

以上是一个简单的链表实现，可以通过添加其他方法来进行更多操作。这个实现只包含了单向链表，如果需要实现双向链表或循环链表，需要在节点类中添加相应的成员变量，并在链表类中修改对应的方法。

**链表的优点**是可以快速添加、删除元素，但其缺点是访问任意位置元素的时间复杂度为O(n)，因此不适合用于需要频繁随机访问元素的场合。