2019年08月19日(星期一)  农历:己亥年七月十九
  • 首页
  • JAVA
  • 数据结构之双向链表的Java实现

作者:三年。分类: JAVA

 单链表只能从前往后遍历,如果链表的长度较大,遍历到链表后半部分的时候想要往前查找,就只能回到开头,重新遍历了。

双向链表提供了这个能力,即允许前向遍历,也允许后向遍历整个链表。原因是双向链表的每个节点都有两个指向其他节点的引用。但这也是其缺点,因为在插入、删除的时候需要处理四个链接点的引用, 占用的空间也大了一些。如将头节点和尾节点链接起来,即成为双向循环链表。

下面是java代码:

package test;

public class DoubleLink {

public Link first;

public Link last;

public DoubleLink() {// 构造器,初始化

this.first = null;

this.last = null;

}

public boolean isEmpty() {// 判断是否为空

return first == null;

}

public void insertFirst(int idata) {// 将元素插入链表开头

Link link = new Link(idata);

if (isEmpty())

last = link;// 如果为空,last需要改变

else

first.previous = link;// 非空,则要在first前插入

link.next = first;

first = link;

}

public void insertLast(int idata) {// 插入链表结尾

Link link = new Link(idata);

if (isEmpty())

first = link;

else

last.next = link;

link.previous = last;

last = link;

}

public boolean insertAfter(int key, int idata) {// 在某项元素后插入

Link current = first;

while (current.idata != key) {//从头开始查找

current = current.next;

if (current == null)//到表尾也没有找到

return false;

}

Link link = new Link(idata);

if (current == last) {

link.next = null;

last = link;

} else {

link.next = current.next;

current.next.previous = link;

}

link.previous = current;

current.next = link;

return true;

}

public Link delectKey(int key) {// 删除某项元素

Link current = first;

while (current.idata != key) {

current = current.next;

if (current == null)

return null;

}

if (current == first)

first = current.next;

else

current.previous.next = current.next;

if (current == last)

last = current.previous;

else

current.next.previous = current.previous;

return current;

}

public Link delectFirst() {// 删除链表开头元素

Link temp = first;

if (first.next == null)// 只有一个元素

last = null;

else

first.next.previous = null;//first节点的next字段引用的链节点的previous字段

first = first.next;

return temp;

}

public Link delectLast() {// 删除链表最后的元素

Link temp = last;

if (first.next == null)

first = null;

else

last.previous.next = null;

last = last.previous;

return temp;

}

public void showFirst() {// 前向展示

Link current = last;

while (current != null) {

current.showLink();

current = current.previous;

}

}

public void showLast() {// 后向展示

Link current = first;

while (current != null) {

current.showLink();

current = current.next;

}

}

public static void main(String[] args) {

DoubleLink dlink = new DoubleLink();

dlink.insertFirst(1);

dlink.insertFirst(2);

dlink.insertFirst(3);

dlink.showFirst();

dlink.insertLast(4);

dlink.insertLast(5);

dlink.showFirst();

}

}

class Link {

public int idata;// 存放的数据

public Link previous;// 对前一项的引用

public Link next;// 对后一项的引用

public Link(int idata) {

this.idata = idata;

}

public void showLink() {

System.out.print(idata + " ");

}

}

温馨提示如有转载或引用以上内容之必要,敬请将本文链接作为出处标注,谢谢合作!

已有 0/1386 人参与

发表评论:



手Q扫描加入Java初学者群