Java链表——菜鸟学数据结构（一）

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

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

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

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;
	}

	

}

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&lt;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());
	}

}

package ds;

public class Tester {

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

}