链表——双链表

双链表

🟡前言

21天挑战赛第三周，本文将介绍有关双链表的知识

活动地址：CSDN21天学习挑战赛

🟡概述

1️⃣定义

双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点

2️⃣示意图

🟡API设计

1.节点API设计

1️⃣构造方法

Node(T t,Node pre,Node next)

：创建Node对象

2️⃣成员变量

• T item：存储数据
• Node next：指向下一个结点
• Node pre：指向上一个结点

2.双链表API设计

1️⃣构造方法

TowWayLinkList()

：创建LinkList对象

2️⃣成员方法

• public void clear()：将一个线性表置为空表
• public boolean isEmpty()：判断当前线性表是否为空表
• public int length()：获取线性表的长度
• public T get(int i)：获取当前索引对应元素
• public void insert(int i, T t)：向线性表中索引值为i处前添加元素t
• public void insert(T t)：向线性表中添加元素t
• public T remove(int i)：删除i处元素值，并返回该元素
• public int indexOf(T t) ：查找t元素第一次出现位置
• public T getFirst()：获取第一个元素
• public T getLast()：获取最后一个元素

3️⃣成员内部类

private class Node

：节点类

4️⃣成员变量

• private Node head：记录头节点
• private Node last：记录尾结点
• private int N：记录链表长度

🟡代码实现

publicclassTowWayLinkList<T>implementsIterable<T>{//首结点privateNode head;//最后一个结点privateNode last;//链表的长度privateintN;//结点类privateclassNode{publicNode(T item,Node pre,Node next){this.item = item;this.pre = pre;this.next = next;}//存储数据publicT item;//指向上一个结点publicNode pre;//指向下一个结点publicNode next;}publicTowWayLinkList(){//初始化头结点和尾结点this.head =newNode(null,null,null);this.last=null;//初始化元素个数this.N=0;}//清空链表publicvoidclear(){this.head.next=null;this.head.pre=null;this.head.item=null;this.last=null;this.N=0;}//获取链表长度publicintlength(){returnN;}//判断链表是否为空publicbooleanisEmpty(){returnN==0;}//获取第一个元素publicTgetFirst(){if(isEmpty()){returnnull;}return head.next.item;}//获取最后一个元素publicTgetLast(){if(isEmpty()){returnnull;}return last.item;}//插入元素tpublicvoidinsert(T t){if(isEmpty()){//如果链表为空：//创建新的结点Node newNode =newNode(t,head,null);//让新结点称为尾结点
            last=newNode;//让头结点指向尾结点
            head.next=last;}else{//如果链表不为空Node oldLast = last;//创建新的结点Node newNode =newNode(t, oldLast,null);//让当前的尾结点指向新结点
            oldLast.next=newNode;//让新结点称为尾结点
            last = newNode;}//元素个数+1N++;}//向指定位置i处插入元素tpublicvoidinsert(int i,T t){//找到i位置的前一个结点Node pre = head;for(int index=0;index<i;index++){
            pre=pre.next;}//找到i位置的结点Node curr = pre.next;//创建新结点Node newNode =newNode(t, pre, curr);//让i位置的前一个结点的下一个结点变为新结点
        pre.next=newNode;//让i位置的前一个结点变为新结点
        curr.pre=newNode;//元素个数+1N++;}//获取指定位置i处的元素publicTget(int i){Node n = head.next;for(int index=0;index<i;index++){
            n=n.next;}return n.item;}//找到元素t在链表中第一次出现的位置publicintindexOf(T t){Node n = head;for(int i=0;n.next!=null;i++){
            n=n.next;if(n.next.equals(t)){return i;}}return-1;}//删除位置i处的元素，并返回该元素publicTremove(int i){//找到i位置的前一个结点Node pre = head;for(int index=0;index<i;index++){
            pre=pre.next;}//找到i位置的结点Node curr = pre.next;//找到i位置的下一个结点Node nextNode= curr.next;//让i位置的前一个结点的下一个结点变为i位置的下一个结点
        pre.next=nextNode;//让i位置的下一个结点的上一个结点变为i位置的前一个结点
        nextNode.pre=pre;//元素的个数-1N--;return curr.item;}@OverridepublicIterator<T>iterator(){returnnewTIterator();}privateclassTIteratorimplementsIterator{privateNode n;publicTIterator(){this.n=head;}@OverridepublicbooleanhasNext(){return n.next!=null;}@OverridepublicObjectnext(){
            n=n.next;return n.item;}}}

🟡结语

双链表的实现与单链表不同，对于删除元素后的指向会比较容易搞错，所以比较难以理解，下一篇文章将讲述有关快慢指针的问题