数据结构与算法(4) -- list、queue以及stack (2)

iterator erase( iterator itr ) { Node *p = itr.current; iterator retVal( p->next ); p->prev->next = p->next; p->next->prev = p->prev; delete p; --theSize; return retVal; } iterator erase( iterator from, iterator to ) { for( iterator itr = from; itr != to; ) itr = erase( itr ); return to; }

直观上看我们只要删除1和2号线，增加3和4号线就可以了。代码就是上面的代码哈，很简单。但是，经常容易犯得错误是：忘记先保存删除节点的位置。那么在1与2号线删除之后就再也无法释放其资源了哈，这就是第一行代码 Node *p = itr.current; 的用意。第二行代码 iterator retVal( p->next ); 是为了删除之后仍然能够得到有效的迭代器。

插入

插入操作也是类型的，只不过这里用了一个较为看上去复杂的操作 p->prev = p->prev->next = new Node{ x, p->prev, p } 。记住，c++赋值语句，是从右往左执行的。结合图，也就不难理解这句话了。

// Insert x before itr. iterator insert( iterator itr, const Object & x ) { Node *p = itr.current; ++theSize; return iterator( p->prev = p->prev->next = new Node{ x, p->prev, p } ); } // Insert x before itr. iterator insert( iterator itr, Object && x ) { Node *p = itr.current; ++theSize; return iterator( p->prev = p->prev->next = new Node{ std::move( x ), p->prev, p } ); } 其他--stl/java

stl里list的实现实际上稍有出入，主要体现在内存分配与构造。实在是能力有限，在这里不敢瞎说。推荐大家阅读侯捷老师的《STL源码剖析》。另外java里的迭代器需要实现Iterator接口就好了。

关于queue与stack的基于node的实现就不赘述了。另外dequeue也可基于node实现，但是stl里是基于分段连续线性空间实现的，如果有可能会在后续的博客中详细讲述。

最后给一个我之前写的dequeue-java版本作为结束。

import java.util.Iterator; import java.util.NoSuchElementException; public class Deque<Item> implements Iterable<Item> { private Node first = null; private Node last = null; private int size = 0; public Deque() { } private class Node{ Item item; Node next; Node previous; } public boolean isEmpty() { return first==null && last==null; } public int size() { return size; } public void addFirst(Item item) { if(item==null) throw new IllegalArgumentException(); if(0==size) { //if size==0, let first and last point to item first = new Node(); first.item = item; last = first; }else { Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; oldfirst.previous = first; } size++; } public void addLast(Item item) { if(item==null) throw new IllegalArgumentException(); if(0==size) { //if size==0, let first and last point to item last = new Node(); last.item = item; first = last; }else { Node oldlast = last; last = new Node(); last.item = item; last.previous = oldlast; oldlast.next = last; } size++; } public Item removeFirst() { if(size==0) throw new NoSuchElementException(); Item itemtem = first.item; if(size==1) { first = null; last = null; }else { Node oldfirst = first; first = oldfirst.next; first.previous = null; oldfirst.next = null; oldfirst.item = null; } size--; return itemtem; } public Item removeLast() { if(size==0) throw new NoSuchElementException(); Item itemtem = last.item; if(size==1) { itemtem = last.item; first = null; last = null; }else { Node oldlast = last; last = oldlast.previous; last.next = null; oldlast.previous = null; oldlast.item = null; } size--; return itemtem; } private class DequeIterator implements Iterator<Item>{ private Node current = first; @Override public boolean hasNext() { return current != null; } @Override public Item next() { if(!hasNext()) throw new NoSuchElementException(); Item itemtem = current.item; current = current.next; return itemtem; } public void remove() { throw new UnsupportedOperationException(); } } public Iterator<Item> iterator(){ return new DequeIterator(); } public static void main(String[] args) { // TODO Auto-generated method stub Deque<Integer> deque = new Deque<Integer>(); deque.addFirst(1); deque.addFirst(2); deque.addFirst(3); deque.addLast(4); deque.addLast(5); deque.addLast(6); deque.removeFirst(); deque.removeLast(); deque.removeFirst(); deque.removeLast(); deque.removeFirst(); deque.removeLast(); for (Integer integer : deque) { System.out.println(integer); } } }

See you next time. Happy Coding!!!
我的github