双向链表的四个方法
在正式开始这一章的讨论之前,我们来做一件事情,实现一个双向链表的四个方法:
- 在头部添加
- 在尾部添加
- 在头部删除
- 在尾部删除
如果继续用单向链表的话,为了删除尾部节点,我们需要一个一个指针的指下去,直到倒数第一个节点,然后把其和最后一个节点的指针断开。为了提高效率,我们用空间换时间,采用双向链表。
示例代码:
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
| package ch03;
public class DoubleLink {
public static class DoubleNode{
int data; DoubleNode next; DoubleNode prev;
DoubleNode(int data){ this.data = data; } }
public DoubleNode head; public DoubleNode tail;
public void addAtHead(int data){ DoubleNode curr = new DoubleNode(data);
if (null == head){ head = curr; tail = curr; }else { curr.next = head; head.prev = curr; head = curr; } }
public DoubleNode removeAtHead(){ if (null == head){ return null; }
DoubleNode curr = head; head = head.next; curr.next = null; head.prev = null; return curr; }
public void addAtTail(int data){ DoubleNode curr = new DoubleNode(data);
if (null == tail){ tail = curr; head = curr; }else{ tail.next = curr; curr.prev = tail; tail = curr; } }
public DoubleNode removeAtTail(){ if (null == tail){ return null; } DoubleNode curr = tail; tail = tail.prev; tail.next = null; curr.prev = null;
return curr; }
public void output(){ String rnt = ""; DoubleLink.DoubleNode temp = head; while (temp!=null) { rnt = rnt + temp.data + " "; temp = temp.next; } System.out.println(rnt); }
public static void main(String[] args) { DoubleLink doubleLink = new DoubleLink(); for (int i = 0; i < 10; i++) { doubleLink.addAtHead(9-i); } doubleLink.output(); System.out.println(doubleLink.removeAtHead().data); System.out.println(doubleLink.removeAtTail().data); doubleLink.output(); doubleLink.addAtTail(10); doubleLink.addAtTail(11); doubleLink.addAtTail(12); doubleLink.output(); } }
|
运行结果:
1 2 3 4 5
| 0 1 2 3 4 5 6 7 8 9 0 9 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 10 11 12
|
示例代码:
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
| class DoubleNode: def __init__(self, data): """
:param data: """ self.data = data self.next = None self.prev = None
class DoubleLink: def __init__(self): self.head = None self.tail = None
def addAtHead(self, data): """
:param data: :return: """ curr = DoubleNode(data)
if self.head is None: self.head = curr self.tail = curr else: curr.next = self.head self.head.prev = curr self.head = curr
def removeAtHead(self): """
:return: """ if self.head is None: return None curr = self.head self.head = self.head.next self.head.prev = None curr.next = None return curr
def addAtTail(self, data): """
:param data: :return: """ curr = DoubleNode(data)
if self.tail is None: self.tail = curr self.head = curr else: self.tail.next = curr curr.prev = self.tail self.tail = curr
def removeAtTail(self): """
:return: """ if self.tail is None: return None
curr = self.tail self.tail = self.tail.prev self.tail.next = None curr.prev = None
return curr
def output(self): rnt = "" temp = self.head; while temp is not None: rnt = rnt + str(temp.data) + " " temp = temp.next
print(rnt)
if __name__ == '__main__': doubleLink = DoubleLink() for i in range(10): doubleLink.addAtHead(9 - i)
doubleLink.output() print(doubleLink.removeAtHead().data) print(doubleLink.removeAtTail().data) doubleLink.output() doubleLink.addAtTail(10) doubleLink.addAtTail(11) doubleLink.addAtTail(12) doubleLink.output()
|
运行结果:
1 2 3 4 5
| 0 1 2 3 4 5 6 7 8 9 0 9 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 10 11 12
|
栈和队列
关于栈和队列的特点,我想大家都很清楚了。
栈:先进后出
队列:先进先出
我们把刚刚讨论的双向链表的在头部添加
和在头部删除
两个组合起来,是不是先进后出?栈。
其中在头部添加
对应入栈push()
,在头部删除
对应出栈pop()
。
这种通过链表实现的栈被称为链式栈。
把在头部添加
和在尾部删除
两个组合起来,是不是先进先出?队列。
其中在头部添加
对应入队enqueue()
,在尾部删除
对应出队dequeue()
。
通过链表实现的队列是链式队列。
除了通过链表实现,我们还可以通过数组实现。
通过数组实现的栈被称为顺序栈。
通过数组实现的队列被称为顺序队列。
接下来我们通过数组再实现一遍。
基于数组的栈
我们每次入栈,都插入在数组的尾部。每次出栈,都从数组的尾部取值。这样最方便,入栈和出栈都不用移动数组中的元素。时间复杂度是O(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
| package ch03;
public class ArrayStack {
private int[] array; private int size;
public ArrayStack(int capacity) { this.array = new int[capacity]; size = 0; }
public void resize(){ int[] arrayNew = new int[array.length*2]; System.arraycopy(array, 0, arrayNew, 0, array.length); array = arrayNew; }
public void push(int data){ if(size >= array.length){ resize(); } array[size] = data; size++; }
public Integer pop(){ if (size <= 0){ return null; } int index = size - 1; int rnt = array[index]; size--; return rnt; }
public void output(){ String rnt = ""; for (int i = 0; i < size; i++) { rnt = rnt + array[i] + " "; } System.out.println(rnt); }
public static void main(String[] args) { ArrayStack arrayStack = new ArrayStack(3); System.out.println(arrayStack.pop()); arrayStack.push(1); arrayStack.push(2); arrayStack.push(3); arrayStack.output(); arrayStack.push(4); arrayStack.push(5); arrayStack.push(6); arrayStack.output(); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); arrayStack.output(); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); System.out.println(arrayStack.pop()); }
}
|
运行结果:
1 2 3 4 5 6 7 8 9 10 11
| null 1 2 3 1 2 3 4 5 6 6 5 4 1 2 3 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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| class ArrayStack: def __init__(self, capacity): """
:param capacity: 长度 """ self.array = [None] * capacity self.size = 0
def resize(self): """ 数组扩容 :return: """ array_new = [None] * len(self.array) * 2 for i in range(self.size): array_new[i] = self.array[i] self.array = array_new
def push(self, data): """ 在尾部放入新元素 :param data: :return: """ if self.size >= len(self.array): self.resize() self.array[self.size] = data self.size = self.size + 1
def pop(self): if self.size <= 0: return None index = self.size - 1 self.size = self.size - 1 return self.array[index]
def output(self): """ 输出数组 :return: """ print(self.array[:self.size])
if __name__ == '__main__': arrayStack = ArrayStack(3) print(arrayStack.pop()) arrayStack.push(1) arrayStack.push(2) arrayStack.push(3) arrayStack.output() arrayStack.push(4) arrayStack.push(5) arrayStack.push(6) arrayStack.output() print(arrayStack.pop()) print(arrayStack.pop()) print(arrayStack.pop()) arrayStack.output() print(arrayStack.pop()) print(arrayStack.pop()) print(arrayStack.pop()) print(arrayStack.pop())
|
运行结果:
1 2 3 4 5 6 7 8 9 10 11
| None [1, 2, 3] [1, 2, 3, 4, 5, 6] 6 5 4 [1, 2, 3] 3 2 1 None
|
基于数组的队列
对于基于数组的队列,如果我们入队插入在数组尾部,出队从数组头部出队,这样每次出队的时间复杂度是O(n),如果出队从尾部出队,入队从头部入队,每次入队的时间复杂度是O(n)。
有没有办法让入队和出队的时间复杂度都是O(1)呢?
扇子别动,脑袋动。数组别动,指针动。
数组别动,指针动。
我们在一个数组上定义两个指针,一个是队头,一个是队尾。
所有的入队,都是从队尾入队,队尾指针往后移动。
所有的出队,都是从对头出队,队头指针往后移动。
这样做,入队和出队,时间复杂度都是O(1)了。
但是,这样,队列的空间会越来越小。
如图,此时队列的空间是2,已经无法再塞进任何元素了。
那怎么办呢?
循环数组
我们队头指针与队尾指针在移动到数组最后之后,再回到数组的头部。
那?什么时候说明队列满了呢?
直到(队尾下标 + 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
| package ch03;
public class ArrayQueue {
private int[] array; private int head; private int tail;
public ArrayQueue(int capacity) { this.array = new int[capacity]; }
public int deQueue() throws Exception { if (tail == head){ throw new Exception("队列是空的"); } int data = array[head]; head = (head + 1) % array.length; return data; }
public void enQueue(int data) throws Exception { if ((tail + 1) % array.length == head){ throw new Exception("队列是满的"); } array[tail] = data; tail =(tail+1)%array.length; }
public void output(){ String rnt = ""; for(int i=head; i!=tail; i=(i+1)%array.length){ rnt = rnt + array[i] + " "; } System.out.println(rnt); }
public static void main(String[] args) throws Exception { ArrayQueue arrayQueue = new ArrayQueue(6); arrayQueue.enQueue(1); arrayQueue.enQueue(2); arrayQueue.enQueue(3); arrayQueue.enQueue(4); arrayQueue.enQueue(5); arrayQueue.deQueue(); arrayQueue.deQueue(); arrayQueue.deQueue(); arrayQueue.enQueue(6); arrayQueue.enQueue(7); arrayQueue.enQueue(8); arrayQueue.output(); }
}
|
运行结果:
示例代码:
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
| class ArrayQueue: array = [] head = 0 tail = 0
def __init__(self, capacity): self.array = [None] * capacity self.head = 0 self.tail = 0
def deQueue(self): """ 出队 :return: 出队的元素 """ if self.tail == self.head: raise Exception('队列是空的') data = self.array[self.head] self.head = (self.head + 1) % len(self.array) return data
def enQueue(self, data): """ 入队 :param data: 进入队伍的元素 :return: """ if (self.tail + 1) % len(self.array) == self.head: raise Exception('队列是满的') self.array[self.tail] = data self.tail = (self.tail + 1) % len(self.array)
def output(self): """ 输出 :return: """ rnt = "" i = self.head while i != self.tail: rnt = rnt + str(self.array[i]) + " " i = (i + 1) % len(self.array) print(rnt)
if __name__ == '__main__': arrayQueue = ArrayQueue(6) arrayQueue.enQueue(1) arrayQueue.enQueue(2) arrayQueue.enQueue(3) arrayQueue.enQueue(4) arrayQueue.enQueue(5) arrayQueue.deQueue() arrayQueue.deQueue() arrayQueue.deQueue() arrayQueue.enQueue(6) arrayQueue.enQueue(7) arrayQueue.enQueue(8) arrayQueue.output()
|
运行结果:
关于栈和队列,有很多的应用。例如:
- 深度优先遍历和栈有关
- 广度优先遍历和队列有关
- 递归,和栈有关。
版权声明: 本博客所有文章版权为文章作者所有,未经书面许可,任何机构和个人不得以任何形式转载、摘编或复制。