Java单向链表

Java单向链表

单向链表的特性

和普通的线性结构(如数组)相比,链表结构有以下特点:

  • 单个结点创建非常灵活,普通的线性内存通常在创建的时候就需要设定数据的大小
  • 结点的删除、插入非常方便,不需要像线性结构那样移动剩下的数据
  • 结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LinkListTryAgain {
private Node firstNode;//链表的第一个元素
private Node currentNode;//链表当前元素

class Node{
private int date;//元素内容
private Node next;//元素的下一个节点

public Node(int date) {
this.date = date;
}

@Override
public String toString() {
return "Node{" +
"date=" + date +
", next=" + next +
'}';
}
}
}

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
//增加元素
void Add(int date){
//首个元素不存在,链表为空
if(firstNode==null){
firstNode=new Node(date);
currentNode=firstNode;//置为当前元素
}else {
Node newNode=new Node(date);//新增的节点
currentNode.next=newNode;//新增节点为当前节点的下一个节点
currentNode=currentNode.next;//新增节点置为当前节点
}
System.out.println("新增"+currentNode);
}

查询链表的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
//获取链表长度
int getLength(){
int length=0;
currentNode=firstNode;
while (currentNode!=null){
length++;
currentNode=currentNode.next;

}
System.out.println("长度为"+length);

return length;
}

得到单链表的倒数第N个元素

1
2
3
4
5
6
7
8
9
10
11
12
void getLastIndex(int n){
int length=getLength();
int index=length-n;
currentNode=firstNode;
for(int i=0;i<length;i++){
if(i==index){
System.out.println(currentNode);
}
currentNode=currentNode.next;

}
}

得到单链表的倒数第N个元素,不允许使用长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void getLastIndex2(int n){
currentNode=firstNode;
int i=0;
Node node1=null;
while (currentNode!=null){
if(i==n){
//得到正数第N个
node1=currentNode;
}
i++;
currentNode=currentNode.next;
}

Node node2=firstNode;
currentNode=node1;
while (currentNode!=null){
currentNode=currentNode.next;
node2=node2.next;
}
System.out.println(node2);
}

查找单链表中的中间结点

1
2
3
4
5
6
7
8
9
10
11
void getMiddleNode(){
Node node1=null;
Node node2=null;
node1=firstNode;
node2=firstNode;
while (node1!=null && node2.next!=null){
node1=node1.next;
node2=node2.next.next;
}
System.out.println("中间节点为"+node1);
}