最基础的动态数据结构：链表[数据结构与算法][Java]

最基础的动态数据结构：链表

我们学的数组，栈，队列，都是依照动态数组实现的，而链表是最基础的动态数据结构。

链表 Linked List

  • 数据存储在“节点”（NODE）中
1
2
3
4
class	class	Node{
    E	e;
    Node	next;
}
  • 优点：真正的动态，不需要处理固定容量的问题
  • 缺点：丧失了随机访问的能力

数组最好用于索引有语意的情况。scores[2]

最大的优点：支持快速查询

链表不适合用于索引有语意的情况。

最大的优点：动态。

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 cn.lianbiao;

public class LinkedList<E> {
		
	private class Node{
		public E e;
		public Node next;
		
		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e,null);
		}
		
	    public Node() {
	    	this(null,null);
	    }
	    
	    @Override
	    public String toString() {
	    	package cn.lianbiao;

public class LinkedList<E> {
		
	private class Node{
		public E e;
		public Node next;
		
		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e,null);
		}
		
	    public Node() {
	    	this(null,null);
	    }
	    
	    @Override
	    public String toString() {
	    	return e.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
28
29
30
31
  private Node head;
	    int size;
	    
	    public LinkedList() {
	    	head = null;
	    	size = 0;
	    }
	    
	    //获取链表中的元素个数
	    public int getSize() {
	    	return size;
	    }
	    
	    //返回链表是否为空
	    public boolean isEmpty() {
	    	return size == 0;
	    }
	    
	    //在链表头添加新的元素e
	    public void addFirst(E e) {
//	    	Node node = new Node(e);
//	    	node.next = head;
//	    	head = node;
	    
	    	head = new   private Node head;
	    int size;
	    
	    public LinkedList() {
	    	head = null;
	    	size = 0;
	    }
	    
	    //获取链表中的元素个数
	    public int getSize() {
	    	return size;
	    }
	    
	    //返回链表是否为空
	    public boolean isEmpty() {
	    	return size == 0;
	    }
	    
	    //在链表头添加新的元素e
	    public void addFirst(E e) {
//	    	Node node = new Node(e);
//	    	node.next = head;
//	    	head = node;
	    
	    	head = new Node(e,head);
	    	size++;
	    }
	    
	}
}

在链表中间添加元素

  • 关键：找到要添加的节点的前一个节点
  • 顺序很重要，要先连后断
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
 //在链表的index（0-based）位置添加新的元素e
	    //在链表中不是一个常用的操作，练习用：）
	    public void add(int index,E e) {
	    	if (index < 0 || index > size) {
				throw new IllegalArgumentException("Add failed. illegal index.");
			}
	    	if (index == 0) {
				addFirst(e);
			}else {
				Node prev = head;
				for (int i = 0; i < index - 1; i++) {
					prev = prev.next;
				}
//				Node node = new Node(e);
//				node.next = prev.next;
//				prev.next = node;
				
				prev.next = new Node(e,prev.next);
				size ++;
			}
	    }
	    
	    //在链表末尾添加元素e
	    public void addLast(E e) {
	    	add(size, e);
	    }

		//在链表开头添加元素e
		public void addFirst(E e){
            add( //在链表的index（0-based）位置添加新的元素e
	    //在链表中不是一个常用的操作，练习用：）
	    public void add(int index,E e) {
	    	if (index < 0 || index > size) {
				throw new IllegalArgumentException("Add failed. illegal index.");
			}
	    	if (index == 0) {
				addFirst(e);
			}else {
				Node prev = head;
				for (int i = 0; i < index - 1; i++) {
					prev = prev.next;
				}
//				Node node = new Node(e);
//				node.next = prev.next;
//				prev.next = node;
				
				prev.next = new Node(e,prev.next);
				size ++;
			}
	    }
	    
	    //在链表末尾添加元素e
	    public void addLast(E e) {
	    	add(size, e);
	    }

		//在链表开头添加元素e
		public void addFirst(E e){
            add(0,e);
        }

链表元素的删除

删除索引为2位置的元素

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
  //从链表中删除index（0-based）位置的元素，返回删除的元素
  //在链表中不是一个常用的操作，练习用：）
  public E remove(int index) {
  	if (index < 0 || index >= size) {
	throw new IllegalArgumentException("Remove failed.Index is illegal.");
}
  	
  	Node prev = dummyhead;
  	for (int i = 0; i < index; i++) {
	prev = prev.next;
}
  	
  	Node retNode = prev.next;
  	prev.next = retNode.next;
  	retNode.next = null;
  	size --;
  	
  	return retNode.e;
  }
  
  //从链表中删除第一个元素，返回删除的元素
  public E removeFirst() {
  	return remove(0);
  }
  
  //从链表中删除最后一个元素，返回删除的元素
  public E removeLast() {
  	return remove(size-  //从链表中删除index（0-based）位置的元素，返回删除的元素
  //在链表中不是一个常用的操作，练习用：）
  public E remove(int index) {
  	if (index < 0 || index >= size) {
	throw new IllegalArgumentException("Remove failed.Index is illegal.");
}
  	
  	Node prev = dummyhead;
  	for (int i = 0; i < index; i++) {
	prev = prev.next;
}
  	
  	Node retNode = prev.next;
  	prev.next = retNode.next;
  	retNode.next = null;
  	size --;
  	
  	return retNode.e;
  }
  
  //从链表中删除第一个元素，返回删除的元素
  public E removeFirst() {
  	return remove(0);
  }
  
  //从链表中删除最后一个元素，返回删除的元素
  public E removeLast() {
  	return remove(size-1);
  }
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
package cn.lianbiao;

public class LinkedList<E> {
		
	private class Node{
		public E e;
		public Node next;
		
		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e,null);
		}
		
	    public Node() {
	    	this(null,null);
	    }
	    
	    @Override
	    public String toString() {
	    	return e.toString();
	    }
	}
	    
	    private Node dummyHead;
	    private int size;
	    
	    public  LinkedList() {
	    	dummyHead =new Node(null,null);
	    	size = 0;
	    }
	    
	    //获取链表中的元素个数
	    public int getSize() {
	    	return size;
	    }
	    
	    //返回链表是否为空
	    public boolean isEmpty() {
	    	return size == 0;
	    }
	    
	    //在链表头添加新的元素e
	    public   void addFirst(E e) {
//	    	Node node = new Node(e);
//	    	node.next = head;
//	    	head = node;
	    
//	    	dummyhead = new Node(e,dummyhead);
	    	add(0, e);
	    }
	    
	    //在链表的index（0-based）位置添加新的元素e
	    //在链表中不是一个常用的操作，练习用：）
	    public void add(int index,E e) {
	    	if (index < 0 || index > size) 
				throw new IllegalArgumentException("Add failed. illegal index.");
			
	    	Node prev = dummyHead;
				for (int i = 0; i < index; i++) 
					prev = prev.next;
//				Node node = new Node(e);
//				node.next = prev.next;
//				prev.next = node;
				
				prev.next = new Node(e,prev.next);
				size ++;
	    }
	    
	    //在链表末尾添加元素e
	    public void addLast(E e) {
	    	add(size, e);
	    }
	    
	    //获得链表的第index（0-based）个位置的元素
	    //在链表中不是一个常用的操作，练习用：）
	    public E get(int index)
	    {
	    	if (index < 0 || index >= size) 
	    		throw new IllegalArgumentException("Get failed.illegal index.");
	    	
	    	Node cur = dummyHead.next;
	    	for (int i = 0; i < index; i++) {
				cur = cur.next;
			}
	    	return cur.e;
	    }
	    
	    //获得链表第一个元素
	    public E getFirst() {
	    	return get(0);
	    }
	    
	    //获得链表的最后一个元素
	    public E getLast() {
	    	return get(size - 1);
	    }
	    
	    //修改链表的第index(0 - based)个位置的元素e
	    //在链表中不是一个常用的操作，练习用：）
	    public void set(int index,E e) {
	    	
	    	if (index < 0 || index >= size) 
	    		throw new IllegalArgumentException("Get failed.illegal index.");
	    	
	    	Node cur = dummyHead.next;
	    	for (int i = 0; i < index; i++) {
				cur = cur.next;
			}
	    	
	    	cur.e = e;
	    }
	    
	    //查找链表中是否有元素e
	    public boolean contains(E e) {
	    	
	    	Node cur = dummyHead.next;
	    	while(cur != null) {
	    		if (cur.e.equals(e)) {
					return true;
				}
	    		
	    		cur = cur.next;
	    	}
	    	return false;
	    }
	    
	    //从链表中删除index（0-based）位置的元素，返回删除的元素
	    //在链表中不是一个常用的操作，练习用：）
	    public E remove(int index) {
	    	if (index < 0 || index >= size) 
				throw new IllegalArgumentException("Remove failed.Index is illegal.");
	    	
	    	Node prev = dummyHead;
	    	for (int i = 0 ; i < index ; i ++) 
				prev = prev.next;
	    	
	    	Node retNode = prev.next;
	    	prev.next = retNode.next;
	    	retNode.next = null;
	    	size --;
	    	
	    	return retNode.e;
	    }
	    
	    //从链表中删除第一个元素，返回删除的元素
	    public E removeFirst() {
	    	return remove(0);
	    }
	    
	    //从链表中删除最后一个元素，返回删除的元素
	    public E removeLast() {
	    	return remove(size - 1);
	    }
	    
	    @Override
	    public String toString() {
	    	StringBuilder res = new StringBuilder();
	    	
//	    	Node cur = dummyhead.next;
//	    	while(cur != null) {
//	    		res.append(cur + "->");
//	    		cur = cur.next;
//	    	}
	    	
	    	for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
	    		res.append(cur + "->");
			}
	    	res.append("NULL");
	    	package cn.lianbiao;

public class LinkedList<E> {
		
	private class Node{
		public E e;
		public Node next;
		
		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e,null);
		}
		
	    public Node() {
	    	this(null,null);
	    }
	    
	    @Override
	    public String toString() {
	    	return e.toString();
	    }
	}
	    
	    private Node dummyHead;
	    private int size;
	    
	    public  LinkedList() {
	    	dummyHead =new Node(null,null);
	    	size = 0;
	    }
	    
	    //获取链表中的元素个数
	    public int getSize() {
	    	return size;
	    }
	    
	    //返回链表是否为空
	    public boolean isEmpty() {
	    	return size == 0;
	    }
	    
	    //在链表头添加新的元素e
	    public   void addFirst(E e) {
//	    	Node node = new Node(e);
//	    	node.next = head;
//	    	head = node;
	    
//	    	dummyhead = new Node(e,dummyhead);
	    	add(0, e);
	    }
	    
	    //在链表的index（0-based）位置添加新的元素e
	    //在链表中不是一个常用的操作，练习用：）
	    public void add(int index,E e) {
	    	if (index < 0 || index > size) 
				throw new IllegalArgumentException("Add failed. illegal index.");
			
	    	Node prev = dummyHead;
				for (int i = 0; i < index; i++) 
					prev = prev.next;
//				Node node = new Node(e);
//				node.next = prev.next;
//				prev.next = node;
				
				prev.next = new Node(e,prev.next);
				size ++;
	    }
	    
	    //在链表末尾添加元素e
	    public void addLast(E e) {
	    	add(size, e);
	    }
	    
	    //获得链表的第index（0-based）个位置的元素
	    //在链表中不是一个常用的操作，练习用：）
	    public E get(int index)
	    {
	    	if (index < 0 || index >= size) 
	    		throw new IllegalArgumentException("Get failed.illegal index.");
	    	
	    	Node cur = dummyHead.next;
	    	for (int i = 0; i < index; i++) {
				cur = cur.next;
			}
	    	return cur.e;
	    }
	    
	    //获得链表第一个元素
	    public E getFirst() {
	    	return get(0);
	    }
	    
	    //获得链表的最后一个元素
	    public E getLast() {
	    	return get(size - 1);
	    }
	    
	    //修改链表的第index(0 - based)个位置的元素e
	    //在链表中不是一个常用的操作，练习用：）
	    public void set(int index,E e) {
	    	
	    	if (index < 0 || index >= size) 
	    		throw new IllegalArgumentException("Get failed.illegal index.");
	    	
	    	Node cur = dummyHead.next;
	    	for (int i = 0; i < index; i++) {
				cur = cur.next;
			}
	    	
	    	cur.e = e;
	    }
	    
	    //查找链表中是否有元素e
	    public boolean contains(E e) {
	    	
	    	Node cur = dummyHead.next;
	    	while(cur != null) {
	    		if (cur.e.equals(e)) {
					return true;
				}
	    		
	    		cur = cur.next;
	    	}
	    	return false;
	    }
	    
	    //从链表中删除index（0-based）位置的元素，返回删除的元素
	    //在链表中不是一个常用的操作，练习用：）
	    public E remove(int index) {
	    	if (index < 0 || index >= size) 
				throw new IllegalArgumentException("Remove failed.Index is illegal.");
	    	
	    	Node prev = dummyHead;
	    	for (int i = 0 ; i < index ; i ++) 
				prev = prev.next;
	    	
	    	Node retNode = prev.next;
	    	prev.next = retNode.next;
	    	retNode.next = null;
	    	size --;
	    	
	    	return retNode.e;
	    }
	    
	    //从链表中删除第一个元素，返回删除的元素
	    public E removeFirst() {
	    	return remove(0);
	    }
	    
	    //从链表中删除最后一个元素，返回删除的元素
	    public E removeLast() {
	    	return remove(size - 1);
	    }
	    
	    @Override
	    public String toString() {
	    	StringBuilder res = new StringBuilder();
	    	
//	    	Node cur = dummyhead.next;
//	    	while(cur != null) {
//	    		res.append(cur + "->");
//	    		cur = cur.next;
//	    	}
	    	
	    	for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
	    		res.append(cur + "->");
			}
	    	res.append("NULL");
	    	return res.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
package cn.lianbiao;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedList<Integer> linkedList = new LinkedList<>();
		for (int i = 0; i < 5; i++) {
			linkedList.addFirst(i);
			System.out.println(linkedList);
		}
		
		linkedList.add(2,666);
		System.out.println(linkedList);
	
		linkedList.remove(package cn.lianbiao;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedList<Integer> linkedList = new LinkedList<>();
		for (int i = 0; i < 5; i++) {
			linkedList.addFirst(i);
			System.out.println(linkedList);
		}
		
		linkedList.add(2,666);
		System.out.println(linkedList);
	
		linkedList.remove(2);
		System.out.println(linkedList);
		
		linkedList.removeFirst();
		System.out.println(linkedList);
		
		linkedList.removeLast();
		System.out.println(linkedList);
	}

}

1
2
3
4
5
6
7
8
9
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
4->3->666->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
3->2->0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
4->3->666->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
3->2->1->NULL

使用链表实现栈

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
package cn.shuzu;

import java.util.LinkedList;

public class LinkedListStack<E> implements Stack<E>{

		private LinkedList<E>  list;
		
		public LinkedListStack() {
			list = new LinkedList<>();
		}
		
		@Override
		public int getSize() {
			return list.size();
		}
		
		@Override
		public boolean isEmpty() {
			return list.isEmpty();
		}
		
		@Override
		public void push(E e) {
			list.addFirst(e);
		}
		
		@Override
		public E pop() {
			return list.removeFirst();
		}
		
		@Override
		public E peek() {
			return list.getFirst();
		}
		
		@Override
		public String toString() {
			StringBuilder res = new StringBuilder();
			res.append("Stack: top");
			res.append(list);
			package cn.shuzu;

import java.util.LinkedList;

public class LinkedListStack<E> implements Stack<E>{

		private LinkedList<E>  list;
		
		public LinkedListStack() {
			list = new LinkedList<>();
		}
		
		@Override
		public int getSize() {
			return list.size();
		}
		
		@Override
		public boolean isEmpty() {
			return list.isEmpty();
		}
		
		@Override
		public void push(E e) {
			list.addFirst(e);
		}
		
		@Override
		public E pop() {
			return list.removeFirst();
		}
		
		@Override
		public E peek() {
			return list.getFirst();
		}
		
		@Override
		public String toString() {
			StringBuilder res = new StringBuilder();
			res.append("Stack: top");
			res.append(list);
			return res.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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package cn.shuzu;

import java.util.Random;

public class MainLinkedListStack {

		//测试使用q运行opcount个enqueue和dequeue操作所需要的时间，单位：秒
		private static double testStack(Stack<Integer> stack,int opCount) {
			
			long startTime = System.nanoTime();
			
			Random random = new Random();
			for (int i = 0; i < opCount; i ++) {
				stack.push(random.nextInt(Integer.MAX_VALUE));
			}
			for (int i = 0; i < opCount; i ++) {
				stack.pop();
			}
			
			long endTime = System.nanoTime();
			
			return (endTime - startTime) / 1000000000.0;
		}

		public static void main(String[] args) {
			// TODO Auto-generated method stub
			int opCount = 100000;
			
			ArrayStack<Integer> arrayStack = new ArrayStack<Integer>();
			double time1 = testStack(arrayStack, opCount);
			System.out.println("ArrayQueue,time : " + time1 + "s");
			
			LinkedListStack<Integer> linkedListStack = new LinkedListStack<Integer>();
			double time2 = testStack(linkedListStack, opCount);
			System.out.println("LoopQueue,time : " + time2 + package cn.shuzu;

import java.util.Random;

public class MainLinkedListStack {

		//测试使用q运行opcount个enqueue和dequeue操作所需要的时间，单位：秒
		private static double testStack(Stack<Integer> stack,int opCount) {
			
			long startTime = System.nanoTime();
			
			Random random = new Random();
			for (int i = 0; i < opCount; i ++) {
				stack.push(random.nextInt(Integer.MAX_VALUE));
			}
			for (int i = 0; i < opCount; i ++) {
				stack.pop();
			}
			
			long endTime = System.nanoTime();
			
			return (endTime - startTime) / 1000000000.0;
		}

		public static void main(String[] args) {
			// TODO Auto-generated method stub
			int opCount = 100000;
			
			ArrayStack<Integer> arrayStack = new ArrayStack<Integer>();
			double time1 = testStack(arrayStack, opCount);
			System.out.println("ArrayQueue,time : " + time1 + "s");
			
			LinkedListStack<Integer> linkedListStack = new LinkedListStack<Integer>();
			double time2 = testStack(linkedListStack, opCount);
			System.out.println("LoopQueue,time : " + time2 + "s");
			
		}
	}



1
2
3
//在本机上面测试时间对比
ArrayStack,time : 0.021517699s
LinkedListStack,time : //在本机上面测试时间对比
ArrayStack,time : 0.021517699s
LinkedListStack,time : 0.020234601s

链表实现队列

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
package cn.shuzu;

public class LinkedListQueue<E> implements Queue<E> {
		
	private class Node{
		public E e;
		public Node next;
		
		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e,null);
		}
		
		public Node() {
			this(null,null);
		}
		
		@Override
		public String toString() {
			return e.toString();
		}
	}
	
	private Node head,tail;
	private int size;
	
	public LinkedListQueue() {
		head = null;
		tail = null;
		size = 0;
	}
	
	@Override
	public int getSize() {
		return size;
	}
	
	@Override
	public boolean isEmpty() {
		return size == 0;
	}
	
	@Override
	public void enqueue(E e) {
		if (tail == null) {
			tail = new Node(e);
			head = tail;
		}else {
			tail.next = new Node(e);
			tail = tail.next;
		}
		size ++;
	}
	
	@Override
	public E dequeue() {
		if (isEmpty()) {
			throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
		}
		
		Node retNode = head;
		head = head.next;
		retNode.next = null;
		if (head == null) {
			tail = null;
		}
		size --;
		return retNode.e;
	}
	
	@Override
	public E getFront() {
		if (isEmpty()) {
			throw new IllegalArgumentException("Queue is empty.");
		}
		return head.e;
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Queue: front");
	
	Node cur = head;
	while(cur != null) {
	res.append(cur + "->");
	cur = cur.next;
	}
	
	res.append("Null tail.");
	return res.toString();
	}
	
	public static void main(String[] args) {
		LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
		for (int i = 0; i < 10; i++) {
			queue.enqueue(i);
			System.out.println(queue);
		
			if (i % 3 == package cn.shuzu;

public class LinkedListQueue<E> implements Queue<E> {
		
	private class Node{
		public E e;
		public Node next;
		
		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e,null);
		}
		
		public Node() {
			this(null,null);
		}
		
		@Override
		public String toString() {
			return e.toString();
		}
	}
	
	private Node head,tail;
	private int size;
	
	public LinkedListQueue() {
		head = null;
		tail = null;
		size = 0;
	}
	
	@Override
	public int getSize() {
		return size;
	}
	
	@Override
	public boolean isEmpty() {
		return size == 0;
	}
	
	@Override
	public void enqueue(E e) {
		if (tail == null) {
			tail = new Node(e);
			head = tail;
		}else {
			tail.next = new Node(e);
			tail = tail.next;
		}
		size ++;
	}
	
	@Override
	public E dequeue() {
		if (isEmpty()) {
			throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
		}
		
		Node retNode = head;
		head = head.next;
		retNode.next = null;
		if (head == null) {
			tail = null;
		}
		size --;
		return retNode.e;
	}
	
	@Override
	public E getFront() {
		if (isEmpty()) {
			throw new IllegalArgumentException("Queue is empty.");
		}
		return head.e;
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Queue: front");
	
	Node cur = head;
	while(cur != null) {
	res.append(cur + "->");
	cur = cur.next;
	}
	
	res.append("Null tail.");
	return res.toString();
	}
	
	public static void main(String[] args) {
		LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
		for (int i = 0; i < 10; i++) {
			queue.enqueue(i);
			System.out.println(queue);
		
			if (i % 3 == 2) {
				queue.dequeue();
				System.out.println(queue);
			}
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Queue: front0->Null tail.
Queue: front0->1->Null tail.
Queue: front0->1->2->Null tail.
Queue: front1->2->Null tail.
Queue: front1->2->3->Null tail.
Queue: front1->2->3->4->Null tail.
Queue: front1->2->3->4->5->Null tail.
Queue: front2->3->4->5->Null tail.
Queue: front2->3->4->5->6->Null tail.
Queue: front2->3->4->5->6->7->Null tail.
Queue: front2->3->4->5->6->7->8->Null tail.
Queue: front3->4->5->6->7->8->Null tail.
Queue: front3->4->5->6->7->8->Queue: front0->Null tail.
Queue: front0->1->Null tail.
Queue: front0->1->2->Null tail.
Queue: front1->2->Null tail.
Queue: front1->2->3->Null tail.
Queue: front1->2->3->4->Null tail.
Queue: front1->2->3->4->5->Null tail.
Queue: front2->3->4->5->Null tail.
Queue: front2->3->4->5->6->Null tail.
Queue: front2->3->4->5->6->7->Null tail.
Queue: front2->3->4->5->6->7->8->Null tail.
Queue: front3->4->5->6->7->8->Null tail.
Queue: front3->4->5->6->7->8->9->Null tail.