Java链表——菜鸟学数据结构

<!-- <div class="ad_single"> <script type="text/javascript"> </script> <script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script> </div> -->

数据结构一方面是专业程序员必须熟练掌握的基础知识，另一方面也是非专业人员比较头痛的内容。从本篇文章开始，楠哥将开始连载数据结构的入门知识。本篇为大家介绍Java实现链表。

因为在Java当中，所有的元素都是对象，而且Java抛弃了指针和地址，而使用了引用的方法，所以使用Java构成链表相对简单。链表的好处在于，你可以事先不知道一个数组的大小，而是动态的加载数据，分配空间，从而确保程序的健壮性和效率。Java已经实现了标准的List、ArrayList等，为了更好的阐述链表的结构，下面我们动手写一下自己的链表类。

Java链表的实现首先需要自定义节点类Node，其中包括数据成员和下一个数据成员的引用。在楠哥的代码中，为了方便，就把数据成员定义成了int类型。链表类的成员属性事实上只需要一个头结点header即可，但是为了增加在成员较多情况下的程序的链表的效率，加入tail节点可以更方便的进行操作。如下是链表的样例代码。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

package ds;   public class Node {   private Node next=null; private int data=0;   public Node(){}   public int getData() { return data; }   public void setData(int data) { this.data = data; }   public Node getNext() { return next; }   public void setNext(Node next) { this.next = next; }       }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

package ds;   public class Linklist {   private Node header=null; private Node tail=null;   public Linklist(){}   public void add(int data) { if(header==null) { Node newnode = new Node(); newnode.setData(data); newnode.setNext(null); header=newnode; tail = newnode; } else { Node newnode = new Node(); newnode.setData(data); newnode.setNext(null); tail.setNext(newnode); tail = tail.getNext(); }   }   public int getdata(int index) { Node temp=header; for(int i=0;i<index;i++) { temp= temp.getNext(); } return temp.getData(); }   public void deletehead() { header = header.getNext(); }   public void deletetail() { Node temp = header; while(temp.getNext() != tail) temp=temp.getNext(); tail=temp; tail.setNext(null); }   public void delete(int data) { Node temp=header; while(temp.getNext().getData() != data) temp=temp.getNext(); temp.setNext(temp.getNext().getNext()); }   }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

package ds;   public class Tester {     public static void main(String[] args) {   Linklist l = new Linklist(); for(int i=0;i<10;i++) l.add(i);   for(int i=0;i<10;i++) System.out.print(l.getdata(i)+" ");   System.out.println(); System.out.println(l.getdata(5));   l.deletehead(); for(int i=0;i<9;i++) System.out.print(l.getdata(i)+" "); System.out.println();   l.deletetail(); for(int i=0;i<8;i++) System.out.print(l.getdata(i)+" "); System.out.println();   l.delete(3); for(int i=0;i<7;i++) System.out.print(l.getdata(i)+" "); }   }

======================================================

栈（stack）和队列（queue）是一种最基本、最常用的数据结构。今天我们用Java来实现栈的最基本的功能。栈（stack）的基本操作包括压栈（push）、出栈（pop）和查看栈顶元素（peek）。还经常用到的操作包括获取栈的大小（元素个数）、判断是否为空等此文当中略去，可以通过检测peek（）获取的元素是否为空进行实现。（楠哥计算机学习网www.liubonan.com）

栈的特点是后进先出，因此我们只用一个元素top记录栈顶元素的引用即可。push（）操作通过将栈顶的标示移往新填入的元素实现，peek（）通过返回top的数据实现，pop（）通过将栈顶标示向反方向移动并返回原来的top元素实现。请注意，因为栈当中的标示操作存在向反方向移动，所以Node的定义当中，使用了previous来记录前一个结点的引用，这与linklist稍有不同。本文采用int型作为数据，源码如下。（楠哥计算机学习网www.liubonan.com）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

package ds;   public class Node { private int data; private Node previous;   public Node(){}   public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getPrevious() { return previous; } public void setPrevious(Node previous) { this.previous = previous; }   }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

package ds;   public class Stack { private Node top;   public Stack(int data) { top = new Node(); top.setData(data); top.setPrevious(null); }   public void push(int data) { Node temp = new Node(); temp.setData(data); temp.setPrevious(top); top = temp; }   public boolean empty() { if(top == null) return true; else return false; }   public int pop() { int temp = top.getData(); top = top.getPrevious();   return temp; }   public int peek(){ return top.getData(); }   }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

package ds;   public class Tester {   static public void main(String[] args) { Stack s = new Stack(0);   for(int i=1;i<=10;i++) s.push(i);   while(!s.empty()) System.out.print(s.pop()+" "); }   }