注意:
get、set、add、remove、entry、clear
注意entry的循环:
for (Entry e = header.previous; e != header; e = e.previous) {}
新节点的创建:
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
此时新加节点已知道其前后节点,但其前节点并不知道后节点发生变化,后节点也不知道前节点发生变化,所以分别将新节点赋给他们。
双向链表节点:
private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } }
实现:
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ private transient Entry<E> header = new Entry<E>(null, null, null); public LinkedList() { header.next = header.previous = header; } public E get(int index) { return entry(index).element; } public E set(int index, E element) { Entry<E> e = entry(index); E oldVal = e.element; e.element = element; return oldVal; } // 根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历 private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { //如果较靠近有表头 for (int i = 0; i <= index; i++) e = e.next; } else { //较靠近表尾 for (int i = size; i > index; i--) e = e.previous; } return e; } //默认的添加动作,可以看到这个方法是把新元素添加 到表尾 public boolean add(E e) { addBefore(e, header); //加到头结点之前 ,即表尾 return true; } private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); newEntry.previous.next = newEntry; //将新结点与前后结点相连接 newEntry.next.previous = newEntry; size++; modCount++; return newEntry; } //默认的删除动作是删除链表的第一个元素,所以说在默认情况下,LinkedList其实扮*演的是一个队列的角色 public E remove() { return removeFirst(); } public E removeFirst() { return remove(header.next); } private E remove(Entry<E> e) { if (e == header) throw new NoSuchElementException(); E result = e.element; e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; modCount++; return result; } public void clear() { Entry<E> e = header.next; while (e != header) { Entry<E> next = e.next; e.next = e.previous = null; e.element = null; e = next; } header.next = header.previous = header; size = 0; modCount++; } }
相关推荐
http://msdn.microsoft.com/en-us/library/95z04bas(v=VS.71).aspx 双向链表
双向链表的操作问题 Time Limit: 1000MS Memory Limit: 10000KB Submissions: 111 Accepted: 41 Description 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成...
双向链表
定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x,y以及左结点指针left及右结点指针right。 包含的函数成员包括: (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
详细的介绍了Linux内核中使用的最频繁的双向链表
双向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
实现双向链表的增删改查功能,dos窗口输入输出,可运行,有注释
C 语言版 双向链表 #include #include typedef struct list { int date; struct list *llink; struct list *rlink; }st; st *creat () //创建双向链表 { st *head , *p , *q; head = q = p = NULL; int ...
通过建立双向链表,来实现双向查找,增加和删除的功能
双向链表是一种比较常用的数据结构,在许多场合都有应用。但是,双向链表的节点操作,对于初学者来说或许显得比较繁琐。尤其是,当用链表描述不同的数据结构时,节点结构体的定义都是不同的,这就需要为每一种链表都...
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
原创手操,操作系统课设,线程安全的双向链表,VC6.0,无须配置,可运行
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
用模板类实现了一个简单的双向链表domo。
用双向链表实现大数阶乘 输入一个不限制大小的数 即可计算出它的阶乘
循环双向链表,实现了插入、查找特定的节点、删除等功能,是自己花了半天的时间写完的。
基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
基础数据结构双向链表的C++描述版。实现了双向链表的基本功能。包括拷贝构造函数和IO操作符重载、赋值操作符重载
ALIST是一段基于C语言的数组型双向链表的处理代码,接口简单明了,易于使用,标准C语言开发,可添加在任何C/C++语言工程中,需要注意的是,如果使用了操作系统,请自行在库中修改指向处添加资源锁定,避免因操作系统...