码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


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<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<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)+" ");
	}

}
最近的文章

Java中栈的实现——菜鸟学数据结构(二)

栈(stack)和队列(queue)是一种最基本、最常用的数据结构。今天我们用Java来实现栈的最基本的功能。栈(stack)的基本操作包括压栈(push)、出栈(pop)和查看栈顶元素(peek)。…

Technical, Career继续阅读
更早的文章

哥大在校生所了解到的哥大的CS【楠哥原创】

注:原为发表于一亩三分地论坛http://www.1point3acres.com/bbs/thread-21691-1-1.html?fromuid=14631 自去年3月25日收到哥大的AD以来…

Career, Technical继续阅读
comments powered by Disqus