- 理论：
- 链表定义 ：通过指针串联在一起的线性结构，每个节点由两部分组成，一个是数据域，一个是指针域（放指向下一个节点的指针），入口节点称头节点head，最后一个节点的指针域指向null
- 类型：
- 单链表
- 双链表：每个节点有两个指针域，一个prev一个next（前驱和后继），双链表可以向前查询也可以向后查询。
- 循环链表：链表首尾相连//可以用来解决约瑟夫环问题
- 存储方式：在内存中不连续分布，通过指针域的指针链接在内存中的各个节点，分布机制取决于操作系统内存管理
- Java定义链表：
/* * @Description: 学生成绩 单向链表，包含:学号、姓名、成绩 * @Autor: SuHe * @Date: 2023-04-13 15:24:44 */ // 节点类 class Node { int data; int np; //成绩 String name;//姓名 Node next; public Node(int data,String name,int np) { this.data = data; this.name = name; this.np = np; next = null; } } // 链表类 public class StuLinkedList { public Node first; public Node last; public boolean isEmpty(){ return first == null;//头节点为null时，链表为空 } public void print() { Node current = first; while(current != null) { System.out.println("[" + current.data + " " + current.name + " " + current.np); current = current.next;//输完一个节点，指针后移一位 } System.out.println(); } public void insert(int data, String name,int np) { Node newNode = new Node(data, name, np); // 如果链表为空，插入的新节点即头节点 if(this.isEmpty()) { first = newNode; last = newNode; } // 链表不为空，将last的指针指向newNode else { last.next = newNode; last = newNode; //指针后移 } } public void delete(Node delNode) { Node curNode = first; Node preNode = null;//delNode的前驱 while( curNode != null) { if(curNode.next == delNode){ preNode = curNode; break; } curNode = curNode.next; } //要删除的是头节点 // 把first 指为 first.next if(delNode.data == first.data) { first = first.next; } // 要删的是尾节点 // 找前驱pre.next指向null else if(last.data == delNode.data) { preNode.next = null; } // 要删的是中间节点 // 找delNode的前驱和后继 else { Node nextNode = delNode.next;//delNode的后继 preNode.next = nextNode; } } } - 特点：插入删除时间复杂度为O(1)，查询时间复杂度为O(n)，数量不固定，适用于频繁增删，较少查询场景
- 题目：
- 203.移除链表元素//
- 707.设计链表//实现如下功能
- get(index) //获取链表中第index个节点的值，如果索引无效，返回-1
- addAtHead(val)//在链表中的第一元素前添加一个值为val的节点
- addAtTail(val)//追加val到链表最后一个元素
- addAtIndex(index,val)//在index前添加val，如果index等于链表长度，插入到链表末尾，如果index大于链表长度，不会插入节点，如果index小于0，在头部插入节点
- deleteAtIndex(index)//如果索引有效，删除链表的第index个节点。
- 206.反转链表//
- 24. 两两交换链表中的节点//
- 19.删除链表的倒数第N个节点//
- 160.链表相交//
- HDU-4841.圆桌问题//Joseph环
406 次浏览