数据结构之链表笔记

前言

其实链表的心法就是“指针的操作”

单链表

单链表的结点包括：data(数据)、next指针
next指针就是指向下一个结点
最后一个结点的next指针指向nil
展示的语言是oc，是面向对象的，那么结点应该就是一个类，然后这个类包括data和next这两个属性；如果是面向过程的语言，如c语言，那么结点应该就是一个结构体
结点包含data，next，那么单链表这个类应该具备两个基本属性头结点和尾结点
接下来，讲一下链表的操作

• 创建空表
  new一个链表类，头结点和尾结点指向nil

• 插入元素

  
  中间插入元素
  尾部插入节点

• 删除元素

  
  删除元素

• 遍历单链表

  
  遍历单链表
• 查找节点
  查找节点3
  ok？从以上几个基本的操作，应该可以看得出来，其实就是对next指针的操作，无论是插入还是删除，都是改变next指针的指向，然后查找的，遍历的，主要是靠头结点来遍历，然后头结点的移动head = head.next其实主要也是靠next指针
  接下来，继续讲双链表

双链表

上面讲到的单链表是单一指向的，就是只有一个方向，如

A -> B -> C -> D

接下来的双链表，就是双向的

A <--> B <--> C <--> D

这句补充一点，对于链表有一个知识点一个要记住，就是结点的组成，比如单链表的结点有data和next
那么双链表的结点会有一个前驱指针和后驱指针和data