你的位置:首页 > Java教程

[Java教程]用java实现一个链表


链表是一种物理存储单元上非连续、非顺序的存储结构,数据节点的逻辑顺序是通过链表中的指针连接次序实现的。

链表----Java实现:

 1 package com.mianshi.easy; 2  3 public class LinkList { 4  5   //节点类是内部类 6   private static class Node { 7     Object data;          //数据 8     Node next;            //下一个数据的引用 9     public Node(Object data){ 10       this.data = data; 11       this.next = null; 12     } 13   } 14  15   /** 16    * 该成员变量head,是为了方便链表接口方法的编写,例如: 17    *     判断链表是否为空,只需判断head是否等于null即可; 18    *     获取链表中节点个数,只需从head依次往下走,直到最后一个节点的next为null 等*/ 19   Node head; 20    21   public LinkList(){ 22     head = null; 23   } 24    25   public void clear(){            //清空链表 26     head = null; 27   } 28    29   public void printAll(){            //遍历打印链表:打印所有的data 30     Node p = head; 31     while(p != null){ 32       System.out.print(p.data+" "); 33       p = p.next; 34     } 35   } 36    37   public boolean isEmpty(){          //判断链表是否为空 38     return head == null; 39   } 40    41   public int length(){            //获得链表长度(节点个数) 42     Node p = head; 43     int sum = 0; 44     while(p != null){ 45       sum++; 46       p = p.next; 47     } 48     return sum; 49   } 50    51   //在指定位置插入元素,下标从0开始 52   public void insert(Object data, int position){ 53      54     if(position < 0 || position > length()){ 55       throw new IndexOutOfBoundsException("访问越界异常"); 56     } 57     Node newNode = new Node(data); 58     if(position == 0){ 59       newNode.next = head; 60       head = newNode; 61     }else if(position >= length() - 1){ 62       get(length() - 1).next = newNode; 63     }else{ 64       newNode.next = get(position); 65       get(position - 1).next = newNode; 66     } 67   } 68  69   //获取指定位置上的节点 70   public Node get(int position){ 71      72     if(position < 0||position >= length()){ 73       throw new IndexOutOfBoundsException("访问越界异常"); 74     } 75     if(position == 0){ 76       return head; 77     } 78     Node p = head; 79     for(int i=0; i<position; i++){ 80       p = p.next; 81     } 82     return p; 83   } 84  85  86   //主方法,验证链表类的功能 87   public static void main(String[] args) { 88  89     LinkList ll = new LinkList(); 90     ll.insert(10, 0); 91     ll.insert(20, 1); 92     ll.insert(30, 0); 93     ll.insert(40, 1); 94     ll.insert(50, 4); 95     ll.printAll(); 96      97     System.out.println(); 98     //访问越界位置时,将会抛出异常,程序中没有try{}catch{}finally{}处理 99     //程序会在异常处跳出来,不再运行下面部分100     System.out.println(ll.get(5));101     102     //这部分代码不再运行103     ll.insert(90, 0);104     ll.insert(80, 1);105     ll.printAll();106   }107 }

结果:

30 40 10 20 50 Exception in thread "main" java.lang.IndexOutOfBoundsException: 访问越界异常  at com.mianshi.easy.LinkList.get(LinkList.java:73)  at com.mianshi.easy.LinkList.main(LinkList.java:100)

 

链表的关键点在于它对每个节点的next指针(或引用),不论是插入、删除或修改操作,都是去改变某个或某些节点的next指向。