数据结构-链表的简单操作代码实现3-LinkedList【Java版】

写在前:

本篇博客主要介绍关于双向链表的一些简答操作实现，其中有有部分代码的实现和前两篇博客中的单向链表是相类似的。例如：查找链表中是否包含关键字key、求链表的长度等。

其余的涉及到prev指向的需要特别注意，区分和单向链表之间的差异。

目录

写在前:

0.首先定义一个结点

1.双向链表-头插法

2.双向链表-尾插法

3.双向链表-任意位置插

4.打印双向链表

5.求双向链表的长度

6.找到双向链表中下标为index的元素

7.查找双向链表中是否包含关键字key

8.删除双向链表中第一个值为key的结点

9.删除双向链表中所有值为key的结点

10.清空双向链表

---

0.首先定义一个结点

实现双向链表，首先需要自己定义一个结点，结点中包含三个域：val、prev、next;

定义头结点的引用head

定义尾结点的引用last

    static class ListNode{public int val;public ListNode prev;//前驱public ListNode next;//后继//提供一个构造方法public ListNode(int val){this.val = val;}}public ListNode head;//代表当前链表头结点的引用public ListNode last;//代表当前链表尾结点的引用

1.双向链表-头插法

    public void addFirst(int data){ListNode node = new ListNode(data);if(head == null){head = node;last = node;}else {node.next = head;head.prev = node;head = node;}}

2.双向链表-尾插法

    public void addLast(int data){ListNode node = new ListNode(data);if(head == null){head = node;last = node;}else{last.next = node;node.prev = last;last = node;}}

3.双向链表-任意位置插

    public void addIndex(int index,int data){//首先判断插入位置的合法性；if(index < 0 || index >size()){throw new ListIndexOutOfException();}//当下标为0-头插法if(index == 0){addFirst(data);return;}//当下标为size，尾插法if(index == size()){addLast(data);return;}//排除其他情况--正常插入//定义结点cur指向需要插入到的index位置ListNode cur = findIndex(index);ListNode node = new ListNode(data);cur.prev.next = node;node.prev = cur.prev;node.next = cur;cur.prev = node;}

4.打印双向链表

    public void display(){ListNode cur = head;while(cur != null){System.out.print(cur.val +" ");cur = cur.next;}System.out.println();}

5.求双向链表的长度

    public int size(){int len = 0;ListNode cur = head;while(cur != null){len++;cur = cur.next;}return len;}

6.找到双向链表中下标为index的元素

    private ListNode findIndex(int index){ListNode cur = head;while (index != 0){cur = cur.next;index--;}return cur;}

7.查找双向链表中是否包含关键字key

    public boolean contains(int key){ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}

8.删除双向链表中第一个值为key的结点

    public void remove(int key){ListNode cur = head;while (cur != null){//判断cur的值和所要删除的值是否相同//相同if(cur.val == key){//这里需要分多种情况//1.删除的是头结点if(cur == head){head = head.next;//如果链表中有多个结点，则需要将前head.prev置空if(head != null){head.prev = null;}}else {//2.删除的不是头结点//删除的是尾巴结点if(cur.next == null){last = last.prev;cur.prev.next = null;}else {//删除的是中间结点cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;//不相同}cur = cur.next;}}

9.删除双向链表中所有值为key的结点

    public void removeAllKey(int key){ListNode cur = head;while (cur != null){//判断cur的值和所要删除的值是否相同//相同if(cur.val == key){//这里需要分多种情况//1.删除的是头结点if(cur == head){head = head.next;//如果链表中有多个结点，则需要将前head.prev置空if(head != null){head.prev = null;}}else {//2.删除的不是头结点//删除的是尾巴结点if(cur.next == null){last = last.prev;cur.prev.next = null;}else {//删除的是中间结点cur.prev.next = cur.next;cur.next.prev = cur.prev;}}//不相同}cur = cur.next;}}

10.清空双向链表

    public void clear(){ListNode cur = head;while (cur != null){ListNode curNext = cur.next;cur.next = null;cur.prev = null;cur = curNext;}head = null;last = null;}