🟡前言
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
:记录链表长度
🟡代码实现
public class TowWayLinkList<T> implements Iterable<T> { //首结点 private Node head; //最后一个结点 private Node last; //链表的长度 private int N; //结点类 private class Node{ public Node(T item, Node pre, Node next) { this.item = item; this.pre = pre; this.next = next; } //存储数据 public T item; //指向上一个结点 public Node pre; //指向下一个结点 public Node next; } public TowWayLinkList() { //初始化头结点和尾结点 this.head = new Node(null,null,null); this.last=null; //初始化元素个数 this.N=0; } //清空链表 public void clear(){ this.head.next=null; this.head.pre=null; this.head.item=null; this.last=null; this.N=0; } //获取链表长度 public int length(){ return N; } //判断链表是否为空 public boolean isEmpty(){ return N==0; } //获取第一个元素 public T getFirst(){ if (isEmpty()){ return null; } return head.next.item; } //获取最后一个元素 public T getLast(){ if (isEmpty()){ return null; } return last.item; } //插入元素t public void insert(T t){ if (isEmpty()){ //如果链表为空: //创建新的结点 Node newNode = new Node(t,head, null); //让新结点称为尾结点 last=newNode; //让头结点指向尾结点 head.next=last; }else { //如果链表不为空 Node oldLast = last; //创建新的结点 Node newNode = new Node(t, oldLast, null); //让当前的尾结点指向新结点 oldLast.next=newNode; //让新结点称为尾结点 last = newNode; } //元素个数+1 N++; } //向指定位置i处插入元素t public void insert(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 = new Node(t, pre, curr); //让i位置的前一个结点的下一个结点变为新结点 pre.next=newNode; //让i位置的前一个结点变为新结点 curr.pre=newNode; //元素个数+1 N++; } //获取指定位置i处的元素 public T get(int i){ Node n = head.next; for(int index=0;index<i;index++){ n=n.next; } return n.item; } //找到元素t在链表中第一次出现的位置 public int indexOf(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处的元素,并返回该元素 public T remove(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; //元素的个数-1 N--; return curr.item; } @Override public Iterator<T> iterator() { return new TIterator(); } private class TIterator implements Iterator{ private Node n; public TIterator(){ this.n=head; } @Override public boolean hasNext() { return n.next!=null; } @Override public Object next() { n=n.next; return n.item; } } }
🟡结语
双链表的实现与单链表不同,对于删除元素后的指向会比较容易搞错,所以比较难以理解,下一篇文章将讲述有关快慢指针的问题