Fork me on GitHub

Java 数据结构之链表

发表于 | 分类于 | | 阅读次数:
字数统计: 2,883 | 阅读时长 ≈ 14

前言

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

由于链表不必按照顺序存储，故在插入数据时可以达到O(1)的复杂度，但是查找的时候就需要遍历，时间复杂度为O(n)。

分类

链表根据实现方式一般有三种分类：单向链表、循环链表、双向链表。

单向链表

单向链表指的是链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向。也就是一种线性链表。

图示：

upload successful

普通单向链表

用Java代码实现一普通的单向链表。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
public class SingleLinkList {

	    private int size;//链表节点的个数
	    private Node head;//头节点
	    
	    public SingleLinkList(){
	        size = 0;
	        head = null;
	    }
	    
	    //链表的每个节点类
	    private class Node{
	        private Object data;//每个节点的数据
	        private Node next;//每个节点指向下一个节点的连接
	        
	        public Node(Object data){
	            this.data = data;
	        }
	    }
	    
	    //在链表头添加元素
	    public Object addHead(Object obj){
	        Node newHead = new Node(obj);
	        if(size == 0){
	            head = newHead;
	        }else{
	            newHead.next = head;
	            head = newHead;
	        }
	        size++;
	        return obj;
	    }
	    
	    //在链表头删除元素
	    public Object deleteHead(){
	        Object obj = head.data;
	        head = head.next;
	        size--;
	        return obj;
	    }
	    
	    //查找指定元素，找到了返回节点Node，找不到返回null
	    public Node find(Object obj){
	        Node current = head;
	        int tempSize = size;
	        while(tempSize > 0){
	            if(obj.equals(current.data)){
	                return current;
	            }else{
	                current = current.next;
	            }
	            tempSize--;
	        }
	        return null;
	    }
	    
	    //删除指定的元素，删除成功返回true
	    public boolean delete(Object value){
	        if(size == 0){
	            return false;
	        }
	        Node current = head;
	        Node previous = head;
	        while(current.data != value){
	            if(current.next == null){
	                return false;
	            }else{
	                previous = current;
	                current = current.next;
	            }
	        }
	        //如果删除的节点是第一个节点
	        if(current == head){
	            head = current.next;
	            size--;
	        }else{//删除的节点不是第一个节点
	            previous.next = current.next;
	            size--;
	        }
	        return true;
	    }
	    
	    //判断链表是否为空
	    public boolean isEmpty(){
	        return (size == 0);
	    }
	    
	    //显示节点信息
	    public String display(){
	    	
	    	StringBuilder sb=new StringBuilder();
	        if(size >0){
	            Node node = head;
	            int tempSize = size;
	            if(tempSize == 1){//当前链表只有一个节点
	                sb.append("["+node.data+"]");
	                return sb.toString();
	            }
	            while(tempSize>0){
	                if(node.equals(head)){
	                    sb.append("["+node.data+"->");
	                }else if(node.next == null){
	                	sb.append(node.data+"]");
	                }else{
	                	sb.append(node.data+"->");
	                }
	                node = node.next;
	                tempSize--;
	            }
	            return sb.toString();
	        }else{//如果链表一个节点都没有，直接打印[]
	        	sb.append("[]");
	        	return sb.toString();
	        }     
	    }
}

栈具有先进后出的原则，所以单向链表可以用来实现栈。Java代码如下：

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
public class StackSingleLinkList {

	public class StackSingleLink {
	    private SingleLinkList link;
	    
	    public StackSingleLink(){
	        link = new SingleLinkList();
	    }
	    
	    //添加元素
	    public void push(Object obj){
	        link.addHead(obj);
	    }
	    
	    //移除栈顶元素
	    public Object pop(){
	        Object obj = link.deleteHead();
	        return obj;
	    }
	    
	    //判断是否为空
	    public boolean isEmpty(){
	        return link.isEmpty();
	    }
	    
	    //打印栈内元素信息
	    public String display(){
	        return link.display();
	    }
	}
}

我们可以看出，如果对链表的最后一个元素进行操作，需要遍历到链表尾部，在进行操作，十分消耗资源。

双端链表

还有一种单向链表称为双端链表。这种链表有一个特点，即在链表内添加了对链表尾部的引用。这使得链表可以方便的操作尾部元素。

Java代码实现如下：

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
public class DoublePointLinkList {

	    private Node head;//头节点
	    private Node tail;//尾节点
	    private int size;//节点的个数
	    
	    private class Node{
	        private Object data;
	        private Node next;
	        
	        public Node(Object data){
	            this.data = data;
	        }
	    }
	    
	    public DoublePointLinkList(){
	        size = 0;
	        head = null;
	        tail = null;
	    }
	    
	    //链表头新增节点
	    public void addHead(Object data){
	        Node node = new Node(data);
	        if(size == 0){//如果链表为空，那么头节点和尾节点都是该新增节点
	            head = node;
	            tail = node;
	            size++;
	        }else{
	            node.next = head;
	            head = node;
	            size++;
	        }
	    }
	    
	    //链表尾新增节点
	    public void addTail(Object data){
	        Node node = new Node(data);
	        if(size == 0){//如果链表为空，那么头节点和尾节点都是该新增节点
	            head = node;
	            tail = node;
	            size++;
	        }else{
	            tail.next = node;
	            tail = node;
	            size++;
	        }
	    }
	    
	    //删除头部节点，成功返回true，失败返回false
	    public boolean deleteHead(){
	        if(size == 0){//当前链表节点数为0
	            return false;
	        }
	        if(head.next == null){//当前链表节点数为1
	            head = null;
	            tail = null;
	        }else{
	            head = head.next;
	        }
	        size--;
	        return true;
	    }
	    //判断是否为空
	    public boolean isEmpty(){
	        return (size ==0);
	    }
	    //获得链表的节点个数
	    public int getSize(){
	        return size;
	    }
	    
	    //显示节点信息
	    public String display(){
	    	
	    	StringBuilder sb=new StringBuilder();
	        if(size >0){
	            Node node = head;
	            int tempSize = size;
	            if(tempSize == 1){//当前链表只有一个节点
	                sb.append("["+node.data+"]");
	                return sb.toString();
	            }
	            while(tempSize>0){
	                if(node.equals(head)){
	                    sb.append("["+node.data+"->");
	                }else if(node.next == null){
	                	sb.append(node.data+"]");
	                }else{
	                	sb.append(node.data+"->");
	                }
	                node = node.next;
	                tempSize--;
	            }
	            return sb.toString();
	        }else{//如果链表一个节点都没有，直接打印[]
	        	sb.append("[]");
	        	return sb.toString();
	        }     
	    }
}

双端链表可以用来实现队列，相关实现如下：

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
public class QueueLinkList {
	    
	    private DoublePointLinkList dp;
	    
	    public QueueLinkList(){
	        dp = new DoublePointLinkList();
	    }
	    public void insert(Object data){
	        dp.addTail(data);
	    }
	    
	    public void delete(){
	        dp.deleteHead();
	    }
	    
	    public boolean isEmpty(){
	        return dp.isEmpty();
	    }
	    
	    public int getSize(){
	        return dp.getSize();
	    }
	    
	    public String display(){
	        return dp.display();
	    }
}

有序链表

上面所说的单链表数据都是无序的，我们可以构建一个有序的单向链表。即有序链表。

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
public class OrderLinkList {

	    private Node head;
	    private int size;
	    
	    private class Node{
	        private int data;
	        private Node next;
	        
	        public Node(int data){
	            this.data = data;
	        }
	    }

	    public OrderLinkList(){
	    	size=0;
	        head = null;
	    }
	    
	    //插入节点，并按照从小打到的顺序排列
	    public void insert(int value){
	        Node node = new Node(value);
	        Node pre = null;
	        Node current = head;
	        while(current != null && value > current.data){
	            pre = current;
	            current = current.next;
	        }
	        if(pre == null){
	            head = node;
	            head.next = current;
	        }else{
	            pre.next = node;
	            node.next = current;
	        }
	        size++;
	    }
	    
	    //删除头节点
	    public void deleteHead(){
	        head = head.next;
	        size--;
	    }
	    
	    //判断是否为空
	    public boolean isEmpty(){
	        return (size ==0);
	    }
	    
	    //获取长度
	    public int getSize() {
	    	return size;
	    }
	    
	    public String display(){
	    	StringBuilder sb=new StringBuilder();
	        Node current = head;
	        while(current != null){
	            sb.append(current.data+" ");
	            current = current.next;
	        }
	        return sb.toString();
	    }
}

对于有序链表，可以看出，插入或删除某一项最多需要O(n)的时间复杂度（遍历），但如果我们每次只删除最小值，且对插入没有过高要求的话，有序链表是一个不错的选择，比如优先级队列就可以利用有序链表实现。

比如我们插入int数并以最小值为优先级，每次取最小的int值的队列。

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
public class QueueOrderLinkList {
    
    private OrderLinkList dp;
    
    public QueueOrderLinkList(){
        dp = new OrderLinkList();
    }
    public void insert(int data){
        dp.insert(data);
    }
    
    public void delete(){
        dp.deleteHead();
    }
    
    public int getSize() {
    	return dp.getSize();
    }
    
    public boolean isEmpty() {
    	return dp.isEmpty();
    }
    
    public String display(){
        return dp.display();
    }
}

单向链表的用途可以说是十分广泛的。

双向链表

双向链表即是这样一个有序的结点序列，每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针，即left和right。left指针指向左边结点，right指针指向右边结点。所以双向链表是可以从两个方向进行遍历的。

图示：

upload successful

双向链表的Java实现：

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
public class DoubleWayLinkList {

	    private Node head;//表示链表头
	    private Node tail;//表示链表尾
	    private int size;//表示链表的节点个数
	    
	    private class Node{
	        private Object data;
	        private Node next;
	        private Node prev;
	        
	        public Node(Object data){
	            this.data = data;
	        }
	    }
	    
	    public DoubleWayLinkList(){
	        size = 0;
	        head = null;
	        tail = null;
	    }
	    
	    //在链表头增加节点
	    public void addHead(Object value){
	        Node newNode = new Node(value);
	        if(size == 0){
	            head = newNode;
	            tail = newNode;
	            size++;
	        }else{
	            head.prev = newNode;
	            newNode.next = head;
	            head = newNode;
	            size++;
	        }
	    }
	    
	    //在链表尾增加节点
	    public void addTail(Object value){
	        Node newNode = new Node(value);
	        if(size == 0){
	            head = newNode;
	            tail = newNode;
	            size++;
	        }else{
	            newNode.prev = tail;
	            tail.next = newNode;
	            tail = newNode;
	            size++;
	        }
	    }
	    
	    //删除链表头
	    public Node deleteHead(){
	        Node temp = head;
	        if(size != 0){
	            head = head.next;
	            head.prev = null;
	            size--;
	        }
	        return temp;
	    }
	    
	    //删除链表尾
	    public Node deleteTail(){
	        Node temp = tail;
	        if(size != 0){
	            tail = tail.prev;
	            tail.next = null;
	            size--;
	        }
	        return temp;
	    }
	    
	    //获得链表的节点个数
	    public int getSize(){
	        return size;
	    }
	    //判断链表是否为空
	    public boolean isEmpty(){
	        return (size == 0);
	    }
	    
	    //显示节点信息
	    public String display(){
	    	StringBuilder sb=new StringBuilder();
	        if(size >0){
	            Node node = head;
	            int tempSize = size;
	            if(tempSize == 1){//当前链表只有一个节点
	                sb.append("["+node.data+"]");
	                return sb.toString();
	            }
	            while(tempSize>0){
	                if(node.equals(head)){
	                	sb.append("["+node.data+"->");
	                }else if(node.next == null){
	                	sb.append(node.data+"]");
	                }else{
	                	sb.append(node.data+"->");
	                }
	                node = node.next;
	                tempSize--;
	            }
	            return sb.toString();
	        }else{//如果链表一个节点都没有，直接打印[]
	        	sb.append("[]");
	        	return sb.toString();
	        }        
	    }
}

使用双向链表可以构建双端队列。在这儿就不上代码了，和之前的队列构造类似。

循环链表

循环链表指的是在单向链表和双向链表的基础上，将两种链表的最后一个结点指向第一个结点从而实现循环。

图示：

upload successful

循环链表的Java实现：

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
public class CircleLinkList<T> {
	// 链表的每个节点类
	private class Node<T> {
		private Object data;// 每个节点的数据
		private Node<T> next;// 每个节点指向下一个节点的连接

		public Node(Object data) {
			this.data = data;
		}
	}

	Node<T> head, tail;
	Node<T> p;
	int size = 0;

	public CircleLinkList() {
		this.head = null;
		tail = head;
		p = head;
	}

	public int length() {
		return size;
	}

	/**
	 * 添加节点
	 * 
	 * @param data
	 */
	public void add(T data) {
		Node node = new Node<T>(data);
		if (head == null) {
			head = node;
			tail = head;
			p = head;
			size++;
		} else {
			node.next = head;
			head = node;
			tail.next = head;
			p = head;
			size++;
		}
	}

	/**
	 * 得到数据
	 * 
	 * @param index
	 * @return
	 */
	public T get(int index) {
		int i = 0;
		p = head;
		while (i != index && p != tail) {
			i++;
			p = p.next;
		}
		return (T) p.data;
	}

	/** 
	 * @return
	 */
	public boolean isEmpty() {
		if (head != null)
			return false;
		else
			return true;
	}
}

同样，使用循环链表可以实现循环队列。

总结

链表作为数据结构的一部分，应用是十分广泛的，我们上面说明了几种链表在不同情况下的应用，链表是我们应当学会掌握和使用的。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力！
0%