实现一个链表

Posted on | In , ,

java.util.List是一种链表数据结构的接口，
java.util.ArrayList和LinkedList是链表的实现类。
数组中每一项占用一个特定的位置，通过下标可以直接访问；
而链表寻找一个元素的唯一方法是沿着这个链表一直找下去。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据节点的逻辑顺序是通过链表中的指针（或引用）链接次序实现的。链表中的每个数据元素称为节点（Node），结点可以在运行时动态生成。
每个节点（Node）包括两部分：存储数据元素的数据域（data），存储下一个结点地址的指针域（next）。

N个节点依次构成的链表，称为线性链表。
如果链表对每个节点只包含一个指针域，则称单链表；如果可以从两个方向遍历，则称为双向链表。
实现链表：
1.为了表示一个节点，可以创建一个Node类。它包含两个成员变量：Object（也可以为其它基本类型）类型的数据，和对下一个节点的引用Node类型。
2.另外，由于每个节点肯定需要包含数据，因此Node类可以有一个传入数据参数的构造方法。
3.一般需要创建链表的头结点Node head，它始终表示链表的头一个节点。

1
2
3
4
5
6
7
8
9
class Node{
	Object data;
	Node next; //这种类有时候叫自引用式，因为它包含了一个与自己类型形相同的字段。
	public Node(Object data){ //构造函数，初始化
		super();
		this.data = data;
		this.next = null; //初始化时下一个节点为null
	}
}

一个链表类是需要提供给其它代码使用的，因此它需要提供一些接口方法：
1.判断链表为空isEmpty()
判断head是否为null
2.获取链表节点的个数size()
从head依次往下走，直到最后一个节点的next为null。
3.清空
head = null;
4.得到指定位置的节点或数据
5.插入
（1）在表头插入
把新节点的next指向head；将head指向新节点。
（2）在表尾插入
把最后一个节点的next指向新的节点。
（3）在中间插入
可以在Node类中新增Node previous变量，指向上一个节点。（双向链表）
把原位置的前一个节点的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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**实现一个链表**/
public class MyList{
	private Node head;
	private int size;
	//节点类
	class Node{
		private Object data;
		private Node next;
		public Node(Object data){
			this.data = data;
			this.next = null;
		}
	}
	public Mylist(){
		head = null;
		size = 0;
	}
	//清除链表
	public void clear(){
		head = null;
	}
	//遍历链表
	public void travel(){
		Node p = head;
		while (p != null){
			System.out.print(p.data + " ");
			p = p.next;
		}
	}
	//判断是否为空
	public boolean isEmpty(){
		return head == null;
	}
	//得到节点个数
	public int size(){
		Node p = head;
		sum = 0;
		if (head == null){
			return 0;
		} else {
			while(p != null){
				sum++;
				p = p.next;
			}
		}
		return sum;
	}
	//获取指定位置上的节点
	public Node getNode(int pos){
		if (pos < 0 || pos > size()){
			throw new RuntimeException("下标出错");
		}
		if (pos == 0){
			return head;
		}
		for (int i = 0; i < pos; i++){
			Node p = p.next;
		}
		return p;
	}
	//在指定位置插入元素
	public void insert(Object data, int pos){
		if (pos < 0 || pos > size()){
			throw new RuntimeExcetpion("下标出错");
		}
		Node newNode = new Node(data);
		if (pos == 0){ //插入到表头
			newNode.next = head;
			head = node;
		} else if (pos >= size()-1){ //插入到表尾
			get(size()-1).next = newNode;
			//newNode.next = null;
		} else { //插入到表中
			newNode.next = get(pos);
			get(pos - 1).next = newNode;
		}
	}
	public static void main(String[] args){
		MyList list = new MyList();
		list.insert(10, 0);
		…
	}
}