Java数据结构 |
您所在的位置：网站首页 › 双向循环链表定义 › Java数据结构 |
Java数据结构
|
目录 1.什么是双向链表？ 2.双向链表的基本功能和结构 3.双向链表基本功能详细图解代码实现 1.清空，判空，获得长度功能实现 2.获取第一个元素和最后一个元素 3.添加元素t 4.向指定位置i插入元素t 5.获取指定位置i处的元素 6.找到元素t第一次出现的位置 7.删除位置i的元素，并返回该元素 1.什么是双向链表？要明白什么是双向链表，我们首先得明白什么是链表和什么是单链表？如果对于这个还有疑惑的推荐我的这篇博客，里面有非常详细的图解和代码实现。https://blog.csdn.net/m0_57487901/article/details/120871022?spm=1001.2014.3001.5501 首先我们通过一张直观的图对比单链表和双向链表
通过名字我们就可知它之所以叫双向链表，就是它可以向两头遍历，任意一个结点我可以得到它的前结点和后一个结点。不像单链表具有单向遍历的局限性，而且双向链表同时记录了尾结点last，这样我们每次想得到最后一个结点就不需要从头遍历到末尾了，如果链表很长的话，这样每次循环查询是非常浪费时间的。 2.双向链表的基本功能和结构 public class TwoWayLinkList implements Iterable { //首结点 Node head; //链表的长度 int N; Node last; //结点类 public class Node { //数据域 public T item; //头指针 public Node pre; //尾指针 public Node next; public Node(T item, Node pre, Node next) { this.item = item; this.pre = pre; this.next = next; } } //初始化链表 public TwoWayLinkList() { //初始化头结点和尾结点 this.head = new Node(null, null, null); this.last = new Node(null, null, null); //初始化元素个数 N = 0; }解析：学习数据结构，我们在学习它的基本功能前，一定要明白它的逻辑结构。代码中，首先有一个内部类Node表示为结点，因为一个结点具有指针域和数据域，所以需要用一个类来表示，Node里面首先有表示存放数据的item，因为不清楚存放的数据是什么类型，所以用泛型T表示。同时有两个Node类型的变量pre和next分别记录指向前一个结点和后一个结点。在链表中有两个个Node类型的变量head和last分别表示头指针和尾指针，同时有一个int类型的N记录成员个数。初始化时，只需要建立头结点和尾结点，内部属性都为null，再让N为0即可。 public void clear() 清空链表 public int getLength() 获取链表长度 public boolean isEmpty() 判断链表是否为空 public T getFirst() 获取第一个元素 public T getLast() 获取最后一个元素 public void add(T t) 插入元素t public void insert(int i,T t) 向指定位置i位置插入元素t public T get(int i) 获取指定位置i处的元素 public int indexOf(T t) public T remove(int i) 找到元素t第一次出现的位置 删除位置i处的元素,并返回该元素看上去很多API功能需要实现，但其实大部分都很简单，只要理解就可以自己写出来。 3.双向链表基本功能详细图解代码实现 1.清空，判空，获得长度功能实现 //清空链表 public void clear() { this.head.next = null; this.last = null; this.N = 0; } //获取链表长度 public int getLength() { return N; } //判断链表是否为空 public boolean isEmpty() { return N == 0; }解析：这里我需要提醒大家，虽然头结点我们一般不存储元素，但是尾结点我们是可以存储的元素的，不要硬性思维。清空时，我们需要让头结点的next为null，这样无法从头进入链表，尾结点因为也是存储数据的，所以得直接让last为null，同时让N为0。获得链表长度直接返回N。判空也是直接返回N是否等于0的值即可。 2.获取第一个元素和最后一个元素 //获取第一个元素 public T getFirst() { //需要判断链表是否为空 if (isEmpty()) { return null; } return head.next.item; } //获取最后一个元素 public T getLast() { if (isEmpty()) { return null; } return last.item; }解析：无论是获取哪个，我们都需要获取判空操作，养成好习惯，代码一定要考虑进所有情况，否则容易出异常。因为是获取元素，所以我们返回的一定是某个结点的item，第一个元素，说明就是头结点的next的item，最后一个元素就是返回last的item就好。 3.添加元素t //插入元素t public void add(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; } N++; }解析：同样我们需要对链表进行判空操作，如果链表为空，我们需要new一个新节点存入数据t，因为就它一个结点，所以我们把它赋值给last，让它成为尾结点，然后让head指向它即可。如果链表不为空，我们首先需要用一个结点oldLast记录旧的尾结点，同时new一个新节点放入数据t，让它成为新的尾结点last，同时让旧的尾结点oldLast指向它。最后无论怎样都记得让N++。 4.向指定位置i插入元素t //向指定位置i位置插入元素t public void insert(int i,T t){ //找到i位置的前一个节点 Node a=head; for (int j = 0; j < i; j++) { a=a.next; } //找到i位置的节点 Node curr = a.next; //创建新节点 Node newNode = new Node(t, a, curr); //让i位置的前一个节点的下一个节点变为新节点 a.next=newNode; //让i位置的前一个节点变为新节点 curr.pre=newNode; //元素个数加1 N++; }具体的步骤通过下图就能明白，一定要搞清楚每一步的顺序，否则很容易出错，自己可以草稿画图模拟。
|
【本文地址】
今日新闻 |
推荐新闻 |