<!--
<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()+" ");
}
}
|
分享到:
相关推荐
熟悉数组、链表、堆栈、队列、哈希表和二叉树等基本数据结构,以及排序算法(如插入、冒泡、快速、堆、合并排序)和查找算法(如顺序、二分查找)。同时,理解算法的时间和空间复杂度分析,以及递推、递归、穷举、...
8. **算法与数据结构**:虽然Java笔试题不一定涉及复杂算法,但基础的排序、查找算法,以及链表、树等数据结构的运用是必要的。 9. **JVM原理**:理解JVM的工作原理,如内存模型、垃圾回收、类加载机制等,可以帮助...
参赛者可能使用了数组、链表、树、图、哈希表等数据结构,以及排序、搜索、动态规划等算法,来优化性能。 ### 3. 版本控制 "TheLegendOfXianLinSoftware-master"暗示了项目使用了Git进行版本控制,参赛者通过提交、...
4. **数据结构**: - **数组或链表**:可能用来存储蛇的身体部分,以便追踪其位置和移动。 - **栈或队列**:在某些实现中,可能使用栈来处理蛇的移动历史,或者使用队列来规划蛇的前进方向。 5. **算法**: - **...
1. 基础数据结构的实现代码,如链表、栈、队列、树、图等; 2. 算法题目的各种解决方案,包括排序、搜索、动态规划、贪心算法、图算法、字符串处理等; 3. 编程语言特性的应用,如C++的STL库使用、Java的集合框架...
《LeetCode刷题笔记——Java...对于Java程序员来说,通过这个过程可以更好地理解和运用数据结构与算法,为职业生涯打下坚实的基础。在实际的编程工作中,这些知识和经验将发挥重要作用,助你在面对复杂问题时游刃有余。
2. **数据结构**:链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、哈希表等,以及它们在实际问题中的应用。 3. **动态规划**:理解状态转移方程,掌握如何构建最优解,解决最优化问题,如背包问题、最长公共...
8. **数据结构**:在处理座位预订和用户信息时,可能涉及到链表、树、哈希表等数据结构。 9. **异常处理与错误检测**:编写健壮的代码,处理可能出现的异常情况,保证系统稳定性。 10. **文档编写**:需求分析、设计...