数据结构-链表

数据结构-链表

链表是一种基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)，简单来说链表并不像数组存储在一个连续的内存地址空间里，他们可以是不连续的因为他们每个节点保存着下一个节点的引用（地址），所以较之数组来说这是一个优势。

1.单链表

单链表是链表的一种，由节点组成，每个节点包含到下一个节点的指针。

单链表特点：

  • 链表增删元素时间复杂度度为O(1)，查找一个元素复杂度为O(n)
  • 单链表不需要预先分配空间，避免空间浪费
  • 单链表不能进行回溯操作，例如读取倒数几个节点的值
单链表 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 表示一个节点
*/
public class Node {
    //数据域
    public int data;
    //下一节点
    public Node next;

    public Node() {

    }

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

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

单链表的基本操作

  • 链表添加元素

    • 添加头部
    • 添加尾部

  • 链表删除元素

    • 删除指定位置
    • 删除倒数第K个节点

  • 链表查询元素

    • 指定索引
    • 查询倒数第K个节点

  • 其他操作

    • 寻找链表中间元素

    • 旋转单链表

    • 翻转单链表

    • 单链表排序

      • 冒泡排序
      • 插入排序

    • 链表相加求和

    • 删除重复元素

2.双循环链表