数据结构与算法—线性表("线性表详解：数据结构与算法入门")

原创

ithorizon 6个月前 (10-21) 阅读数 15 #后端开发

线性表详解：数据结构与算法入门

一、线性表概述

线性表（Linear List）是数据结构中最基本的一种形式，它是由零个或多个数据元素组成的有限序列。线性表中的元素可以是基本数据类型，也可以是繁复的数据结构。在计算机科学中，线性表是一种抽象数据类型，它提供了对数据元素进行操作的一系列方法。

二、线性表的分类

线性表首要分为两大类：顺序存储的线性表（数组）和链式存储的线性表（链表）。

顺序存储的线性表：元素在内存中连续存储，可以通过下标直接访问。

链式存储的线性表：元素在内存中分散存储，通过指针连接各个元素。

三、线性表的基本操作

线性表的基本操作包括：创建线性表、插入元素、删除元素、查找元素、修改元素、遍历线性表等。

四、顺序存储的线性表（数组）

顺序存储的线性表，也称为数组，是线性表的一种实现做法。数组是一种在内存中连续分配空间的存储结构，可以通过下标直接访问元素。

4.1 创建数组

创建数组时，需要指定数组的长度和类型。以下是一个创建数组的示例代码：


        int[] arr = new int[10]; // 创建一个长度为10的整型数组

4.2 插入元素

在数组中插入元素时，需要先判断数组是否已满，然后移动插入位置后的元素，为新元素腾出空间。以下是一个插入元素的示例代码：


        public static void insertElement(int[] arr, int index, int element) {
            if (index < 0 || index > arr.length) {
                System.out.println("插入位置不合法");
                return;
            }
            if (arr.length == arr.length) {
                System.out.println("数组已满，无法插入");
                return;
            }
            for (int i = arr.length - 1; i > index; i--) {
                arr[i] = arr[i - 1];
            }
            arr[index] = element;
        }

4.3 删除元素

在数组中删除元素时，需要移动删除位置后的元素，填补空缺。以下是一个删除元素的示例代码：


        public static void deleteElement(int[] arr, int index) {
            if (index < 0 || index >= arr.length) {
                System.out.println("删除位置不合法");
                return;
            }
            for (int i = index; i < arr.length - 1; i++) {
                arr[i] = arr[i + 1];
            }
            arr[arr.length - 1] = 0; // 将最后一个元素置为0（或其他标记值）
        }

4.4 查找元素

在数组中查找元素时，可以通过遍历数组或二分查找算法实现。以下是一个线性查找的示例代码：


        public static int linearSearch(int[] arr, int element) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == element) {
                    return i;
                }
            }
            return -1; // 如果未找到，返回-1
        }

4.5 修改元素

在数组中修改元素时，只需要直接访问数组下标，并更新元素值。以下是一个修改元素的示例代码：


        public static void modifyElement(int[] arr, int index, int newValue) {
            if (index < 0 || index >= arr.length) {
                System.out.println("修改位置不合法");
                return;
            }
            arr[index] = newValue;
        }

五、链式存储的线性表（链表）

链式存储的线性表，也称为链表，是线性表的另一种实现做法。链表由一系列节点组成，每个节点包含数据元素和指向下一个节点的指针。

5.1 创建链表

创建链表时，需要定义节点类和链表类。以下是一个创建链表的示例代码：


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

5.2 插入元素

在链表中插入元素时，需要找到插入位置的前一个节点，然后更新指针。以下是一个插入元素的示例代码：


        public void insertElement(int index, int element) {
            if (index < 0) {
                System.out.println("插入位置不合法");
                return;
            }
            ListNode newNode = new ListNode(element);
            if (index == 0) {
                newNode.next = head;
                head = newNode;
                return;
            }
            ListNode prevNode = head;
            for (int i = 0; i < index - 1; i++) {
                prevNode = prevNode.next;
                if (prevNode == null) {
                    System.out.println("插入位置不合法");
                    return;
                }
            }
            newNode.next = prevNode.next;
            prevNode.next = newNode;
        }

5.3 删除元素

在链表中删除元素时，需要找到待删除节点的前一个节点，然后更新指针。以下是一个删除元素的示例代码：


        public void deleteElement(int index) {
            if (index < 0 || head == null) {
                System.out.println("删除位置不合法");
                return;
            }
            if (index == 0) {
                head = head.next;
                return;
            }
            ListNode prevNode = head;
            for (int i = 0; i < index - 1; i++) {
                prevNode = prevNode.next;
                if (prevNode == null || prevNode.next == null) {
                    System.out.println("删除位置不合法");
                    return;
                }
            }
            prevNode.next = prevNode.next.next;
        }

5.4 查找元素

在链表中查找元素时，需要遍历链表，直到找到目标元素或到达链表尾部。以下是一个查找元素的示例代码：


        public int searchElement(int element) {
            ListNode currentNode = head;
            while (currentNode != null) {
                if (currentNode.val == element) {
                    return currentNode.val;
                }
                currentNode = currentNode.next;
            }
            return -1; // 如果未找到，返回-1
        }