`

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()+" ");
	}
 
}
分享到:
评论

相关推荐

    java学习进阶之路,如果从一个菜鸟进阶成大神(csdn)————程序.pdf

    熟悉数组、链表、堆栈、队列、哈希表和二叉树等基本数据结构,以及排序算法(如插入、冒泡、快速、堆、合并排序)和查找算法(如顺序、二分查找)。同时,理解算法的时间和空间复杂度分析,以及递推、递归、穷举、...

    菜鸟的自我修炼——阿里巴巴一道笔试题浅谈

    8. **算法与数据结构**:虽然Java笔试题不一定涉及复杂算法,但基础的排序、查找算法,以及链表、树等数据结构的运用是必要的。 9. **JVM原理**:理解JVM的工作原理,如内存模型、垃圾回收、类加载机制等,可以帮助...

    仙林软件奇侠传——EL比赛.zip

    参赛者可能使用了数组、链表、树、图、哈希表等数据结构,以及排序、搜索、动态规划等算法,来优化性能。 ### 3. 版本控制 "TheLegendOfXianLinSoftware-master"暗示了项目使用了Git进行版本控制,参赛者通过提交、...

    基于Java实现的Snake.zip

    4. **数据结构**: - **数组或链表**:可能用来存储蛇的身体部分,以便追踪其位置和移动。 - **栈或队列**:在某些实现中,可能使用栈来处理蛇的移动历史,或者使用队列来规划蛇的前进方向。 5. **算法**: - **...

    蓝桥杯练习代码_3.zip

    1. 基础数据结构的实现代码,如链表、栈、队列、树、图等; 2. 算法题目的各种解决方案,包括排序、搜索、动态规划、贪心算法、图算法、字符串处理等; 3. 编程语言特性的应用,如C++的STL库使用、Java的集合框架...

    Leetcode-note:刷题笔记

    《LeetCode刷题笔记——Java...对于Java程序员来说,通过这个过程可以更好地理解和运用数据结构与算法,为职业生涯打下坚实的基础。在实际的编程工作中,这些知识和经验将发挥重要作用,助你在面对复杂问题时游刃有余。

    acm教程杭电的

    2. **数据结构**:链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、哈希表等,以及它们在实际问题中的应用。 3. **动态规划**:理解状态转移方程,掌握如何构建最优解,解决最优化问题,如背包问题、最长公共...

    毕设&课程作业_图书馆智能选座系统,包括用户注册登录,预约座位;管理员登录并管理用户信息.zip

    8. **数据结构**:在处理座位预订和用户信息时,可能涉及到链表、树、哈希表等数据结构。 9. **异常处理与错误检测**:编写健壮的代码,处理可能出现的异常情况,保证系统稳定性。 10. **文档编写**:需求分析、设计...

Global site tag (gtag.js) - Google Analytics