经典程序|数据结构之双向链表（Java实现）线性表|数据结构|链表|java|数据

1.双向链表的概述与节点结构

文章图片

2.双向链表的API设计

文章图片

3.双向链表的时间复杂度分析：

文章图片

【经典程序|数据结构之双向链表（Java实现）】4.源码实现：

package linkList; import java.util.Iterator; public class TwoWayLinkList implements Iterable{ //首节点 private Node head; //尾节点 private Node last; //链表长度 private int N; //节点类 private class Node{ //存储数据 public T item; //指向上一个节点 public Node pre; //指向下一个节点 public Node next; //构造方法 public Node(T item,Node pre, Node next){ this.item=item; this.next=next; this.pre=pre; } } //构造方法：创建Twowaylinklist对象 public TwoWayLinkList(){ //初始化头节点,刚开始没有前驱也没有后继，只需要一个节点即可 this.head=new Node(null,null,null); //初始化尾节点,刚开始是没有尾节点的 this.last=null; //初始化元素个数 this.N=0; } //清空链表 public void clear(){ this.head.next=null; this.last.pre=null; this.N=0; } //判断是否为空 public boolean isEmpty(){ return N==0; } //获取链表中元素的个数 public int length(){ return N; } //读取并返回链表中第i个元素的值 public T get(int i){ Node n=head; for(int index=0; index list){ for(String str:list){ System.out.print(str+"->"); } System.out.println(); } /* * 实现Iterable接口返回一个Iterator对象从而实现遍历 * 但是Iterator也是一个接口所以不能直接返回，这时需要一个类来实现Iterator接口从而返回改实现类的对象即可 */ @Override public Iterator iterator() { // TODO Auto-generated method stub return new TIterator(); } private class TIterator implements Iterator{ private Node pre; public TIterator() { this.pre=head; // TODO Auto-generated constructor stub } @Override public boolean hasNext() { // TODO Auto-generated method stub return pre.next!=null; }@Override public Object next() { // TODO Auto-generated method stub pre=pre.next; return pre.item; } } }

5.测试类实现：

package linkList; public class TwoWayLinkListTest { public static void main(String[] args) { TwoWayLinkList> list1=new TwoWayLinkList>(); //测试插入 list1.insert("蜘蛛侠"); list1.insert("蝙蝠侠"); list1.insert("钢铁侠"); list1.insert("美国队长"); list1.foreach(list1); System.out.println("\n---------------------------------------------------"); //测试指定位置插入 list1.insert(2, "雷神"); list1.insert(3,"绿巨人"); list1.foreach(list1); System.out.println("\n---------------------------------------------------"); //测试删除 list1.remove(1); list1.foreach(list1); System.out.println("\n---------------------------------------------------"); //测试获取 System.out.println(list1.get(3)); System.out.println("\n---------------------------------------------------"); //测试第一个元素和最后一个元素 System.out.println(list1.getFirst()); System.out.println(list1.getLast()); System.out.println("\n---------------------------------------------------"); //测试索引 System.out.println(list1.indexOf("钢铁侠")); System.out.println("\n---------------------------------------------------"); //测试长度 System.out.println(list1.length()); //是否为空 System.out.println("是否为空:"+list1.isEmpty()); } }