定义链表：

链表基础

链表的属性

• 单链表
• 双链表
• 循环链表（可以解决约瑟夫环问题）

存储方式

链表在操作系统中的存储一般都不是连续的

链表节点的定义方式

//单链表结构体
struct ListNode(){
    int val; //节点内存储的值
    ListNode *next; //设置单链表的指针
    ListNode(int x) : val(x),next(null){}
};
// C++中可以不加入构造函数，但是初始化的时候就不能赋值；
// 例如：
ListNode *head = new ListNode();
head -> val = 5;

//等同于有构造函数时的：
ListNode *head = new ListNode(5);

typedef struct LinkNode{
    int val;
    struct LinkNode *next;
}LinkList;

class Node{
    int val;
    Node next;
}

class Node{
    int val;
    Node pre;
    Node next;
}

class MyLinkList{

    // 链表的构造方法
    MyLinkList(){
    }

    //获取到第几个节点
    public int get(int index){

    }

    // 在头节点插入
    public void addOfHead(int val){

    }

    // 在尾节点插入
    public void addOfTail(int val){

    }

    // 在指定位置插入
    public void insertOfIndex(int index, int val){

    }

    // 删除指定节点
    public void delete(int index){

    } 
}

链表的常见操作

• 增加一个节点（注意指针）
• 删除一个节点
• 找到一个节点（改该节点的值）

查找的时间复杂度是O(n)，而数组是O(1); 删除的时间复杂度是O(1)，而数组是O(n);

链表的删除操作：

• [[02.移除链表元素]]
• [[06.删除链表中倒数第n个节点]]

链表实现：[[03.设计链表]]

==为什么实现虚拟头节点来进行操作会很复杂==

• 实现了单链表设计实现链表的基本功能
• 实现了循环链表设计实现链表的基本功能
  • 首先头指针的初始化操作
  • 在头插法和尾插法时不同的操作

链表翻转：[[04.翻转链表]]、[[05.两两交换链表中的元素]]

==为什么要使用虚拟头节点来进行操作==

• 普通的链表翻转很简单，注意循环条件，以及双指针的用法即可实现。

链表相交问题：[[07.链表相交]]、[[08.环形链表Ⅱ]]

• 普通的比较很简单
• 环形链表为什么是这样的