疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

数据结构之链表的Java实现


 

  链表:一种离散存储数据的方式,每一个数据块包含一个数据和对下一个数据的引用,首结点无前驱,末结点无后继。链表不按顺序存储,所以插入和删除操作效率很高(O(1)),仅需要改变一两个引用值,不需要移动和复制数据,但是查找效率很低,因为要遍历整个链表。链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。使用链表存储数据的另一个优点就是需要多少内存就有多少,而数组的大小在创建时就固定了。值得一提的是向量,是一种可扩展的数组,它可通过可变长度解决这个问题,但是其一般只允许国定大小的增长(比如,一半),但是效率仍要比链表低。

  链表有很多种不同的类型:单向链表,双向链表以及循环链表。

  链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。单向链表只可向一个方向遍历。

  下面是单链表的java实现。

  package cn.zhf.list;

  public class Link {

  public int idata;//存放int 类型的数据

  public double ddata;//double类型的数据

  public Link next;//对下一个Link对象的引用

  public Link(int id, double dd) {

  idata = id;

  ddata = dd;

  }

  public void diaplay() {

  System.out.println(idata + "," + ddata);

  }

  }

  public class LinkList {

  private Link first;

  public LinkList() {

  first = null;

  }

  public boolean isEmpty() {

  return (first == null);

  }

  //插入一个元素

  public void insertFirst(int id, double dd) {

  Link link = new Link(id, dd);

  link.next = first;//next元素链接first

  first = link;//first元素链接link

  }

  //删除一个元素

  public Link deleteFirst() {

  Link temp = first;

  first = first.next;

  return temp;

  }

  //显示链表的元素

  public void displayLink() {

  Link current = first;

  while (current != null) {

  current.diaplay();

  current = current.next;

  }

  }

  public static void main(String[] args) {

  LinkList list = new LinkList();

  list.insertFirst(12, 12.3);

  list.insertFirst(11, 12.4);

  list.insertFirst(14, 12.5);

  list.displayLink();

  while (!list.isEmpty()) {

  Link flink = list.deleteFirst();

  System.out.print("deleting -->");

  flink.diaplay();

  }

  list.displayLink();

  }

  }

  结果:

  14,12.5

  11,12.4

  12,12.3

  deleting -->14,12.5

  deleting -->11,12.4

  deleting -->12,12.3