目录
链表也是数组的一种形式,由各个节点组成,每个节点包括3部分:val数据域、prev、next;
prev、next代表数据节点的两个指针,分别指向前后节点:
prev存放上一个节点的地址
next存放下一个节点的地址
- //ListNode 代表一个节点
- class Node {
- public Node val; //成员变量,结点里包含的属性
- public Node next;
- public Node prev;
-
- public Node() {
- this.val = val;
- }
- }
-
- //如下函数对双向列表进行增删查改 ---->定义在双向链表定义的类里
- public class MyLinkedList { //head属于链表的属性,只能定义在链表里
-
- //在MyLinkedList类里定义链表的方法
-
- }
- //头插法 ---->定义一个插入节点node ListNode node
- public void addFirst(int data) {
- ListNode node = new ListNode(data); // new一个节点node, node 引用了对象,指代插入的节点
- //如果是第一次插入 判断是否为空链表
- if (this.head == null) {
- this.head = node;
- this.last = node;
- }else {
- node.next = this.head; //插入之后node在head之前,应符合链表结构 并且node作为新的头
- this.head.prev =node;
- this.head = node;
- }
- }
- //尾插法
- public void addLast(int data) {
- ListNode node = new ListNode(data); // new一个节点node, node 引用了对象,指代插入的节点
- ListNode cur = this.head;
- if (cur == null) { //判断是否为空链表
- this.head = node;
- this.last = node;
- }else { //不为空执行遍历操作
- while(cur != null) {
- cur = cur.next;
- }
- this.last.next = node; //head last 代表头节点和尾结点
- node.prev =this.last;
- this.last = node;
- }
- }
-
- //删除第一次出现关键字为key的节点
- public void remove(int key) {
- ListNode cur = this.head;
- while(cur != null) {
- if (cur.val == key) {
- if (cur == head) { //先判断关键字是否在头部
- head = head.next; //关键字在头部执行换头head
- if (head != null) {
- head.prev = null;
- }else {
- last = null;
- }
- } else { //不在头部考虑中间或者尾部,情况也不相同 //删除关键字在中间部位或者尾部
- cur.prev.next = cur.next; //前一个节点指向跳过当前节点指向当前的下一个 尾结点同样适用尾结点指向null
- if (cur.next != null) { //先考虑key关键字在中间
- cur.next.prev = cur.prev; //后往前指
- }else {
- last = last.prev; //考虑key关键字在尾部,,//后往前指
- }
- }
- return;
- }else {
- cur = cur.next;
- }
- }
- }
-
- //删除所有值为key的节点
- public void removeAllKey(int key) {
- ListNode cur = this.head;
- while(cur != null) {
- if (cur.val == key) {
- if (cur == head) { //先判断关键字是否在头部
- head = head.next; //关键字在头部执行换头head
- if (head != null) {
- head.prev = null;
- }else {
- last = null;
- }
- } else { //不在头部考虑中间或者尾部,情况也不相同 //删除关键字在中间部位或者尾部
- cur.prev.next = cur.next; //前一个节点指向跳过当前节点指向当前的下一个 尾结点同样适用尾结点指向null
- if (cur.next != null) { //先考虑key关键字在中间
- cur.next.prev = cur.prev; //后往前指
- }else {
- last = last.prev; //考虑key关键字在尾部,,//后往前指
- }
- }
- }else {
- cur = cur.next;
- }
- }
- }
考虑插入不同位置的情况有差异,分开考虑开头、结尾、中间部分的插入
解析:1.给定位置,要先知道下标的位置,提前先索引,找到插入位置处的节点
2.判断给出的位置是否合法(不能<0,不能超出链表的size())
3.如果插入在头部位置,和头插法一样,引用头插法方法即可
4.如果插入在尾部位置,和尾插法一样,引用尾插法方法即可
- //任意位置插入,第一个数据节点为0号下标
- //解析:分为头插、尾插和中间四个位置的改变
-
- public ListNode searchIndex(int index) { //先找到需要插入的索引位置(指定位置插入)
- ListNode cur = this.head;
- while (index != 0) {
- cur = cur.next;
- index--;
- }
- return cur; //cur为索引index位置处的节点
- }
-
- public void addIndex1(int index,int data) {
- ListNode node = new ListNode(data);
- if (index <0 || index > size()) { //插入索引位置需要判断合法不合法
- System.out.println("index不合法");
- return;
- }
- if (index == 0) { //,索引为0,在头部插入 也即是头插法
- addFirst(data); //引用定义好的头插法,传输插入数据data
- return;
- }
- if (index==size()) { //,索引位置=size()长度,在尾部插入 也即是尾插法
- addLast(data); //引用定义好的尾插法,传输插入数据data
- return;
- }
- ListNode cur = searchIndex(index); //找到索引位置处对应的节点cur
- cur.prev.next = node;
- // node.next = cur.prev.next; //当前cur的地址 //插在中间位置
- node.next = cur; //同上cur=cur.prev.next
- cur.prev = node;
- node.prev = cur.prev;
- }
解析:将所有节点置空即可,从头开始遍历,若cur不为null,将其prev和next置空
最后要将last置空
- //解析:从头开始遍历,若cur不为null,将其prev和next置空
- public void clear() {
- ListNode cur = this.head;
- while(cur != null) {
- ListNode curNext = cur.next;
- cur.prev = null;
- cur.next = null;
- cur = curNext;
- }
- last =null;
- }
-
- // 打印顺序表
- public void display() { //和单链表打印一样
- ListNode cur = this.head;
- while(cur != null) {
- System.out.print(cur.val+" ");
- cur = cur.next;
- }
- System.out.println();
- }
-
- //得到单链表的长度
- public int size() {
- int count = 0; //方法里面的局部变量必须赋初值
- ListNode cur = this.head;
- while(cur != null) {
- count++;
- cur=cur.next;
- }
- return count;
- }
-
- //查找是否包含关键字key是否在单链表当中
- public boolean contains(int key) {
- ListNode cur = this.head;
- while (cur != null) {
- if (cur.val == key) {
- return true;
- }
- cur = cur.next;
- }
- return false;
- }