LinkList(双向链表实现)
2019-08-16 11:27:49来源:博客园 阅读 ()
LinkList(双向链表实现)
LinkedList是用链表结构存储数据的,比较适合数据的动态插入和删除,随机访问和遍历速度比较慢,还提供了List接口i中没有定义的方法,专门用于操作表头和表尾的元素,所以可以当作堆栈、队列和双向队列来使用。LInkedList持有头节点和尾节点的引用,有两个构造器,一个是无参构造器,另一个是传入外部集合构造器,它没有像ArrayList一样的初始大小的构造器。
1 //集合元素个数 2 3 transient int size = 0; 4 5 6 7 //头结点引用 8 9 transient Node<E> first; 10 11 12 13 //尾节点引用 14 transient Node<E> last; 15 16 //无参构造器 17 public LinkedList() {} 18 19 //传入外部集合的构造器 20 public LinkedList(Collection<? extends E> c) { 21 this(); 22 addAll(c); 23 } 24 25 //增(添加) 26 public boolean add(E e) { 27 28 //在链表尾部添加 29 linkLast(e); 30 return true; 31 } 32 33 34 //增(插入) 35 public void add(int index, E element) { 36 37 checkPositionIndex(index); 38 39 if (index == size) { 40 //在链表尾部添加 41 linkLast(element); 42 } else { 43 //在链表中部插入 44 linkBefore(element, node(index)); 45 } 46 } 47 48 49 50 //删(给定下标) 51 public E remove(int index) { 52 53 //检查下标是否合法 54 checkElementIndex(index); 55 return unlink(node(index)); 56 } 57 58 //删(给定元素) 59 public boolean remove(Object o) { 60 if (o == null) { 61 for (Node<E> x = first; x != null; x = x.next) { 62 if (x.item == null) { 63 unlink(x); 64 return true; 65 } 66 } 67 } else { 68 //遍历链表 69 for (Node<E> x = first; x != null; x = x.next) { 70 if (o.equals(x.item)) { 71 //找到了就删除 72 unlink(x); 73 return true; 74 } 75 } 76 } 77 return false; 78 } 79 80 81 82 //改 83 public E set(int index, E element) { 84 85 //检查下标是否合法 86 checkElementIndex(index); 87 88 //获取指定下标的结点引用 89 Node<E> x = node(index); 90 91 //获取指定下标结点的值 92 93 E oldVal = x.item; 94 95 //将结点元素设置为新的值 96 97 x.item = element; 98 99 //返回之前的值 100 101 return oldVal; 102 103 } 104 105 106 //查 107 public E get(int index) { 108 109 //检查下标是否合法 110 checkElementIndex(index); 111 112 //返回指定下标的结点的值 113 return node(index).item; 114 }
LinkedList的添加元素的方法主要是调用LinkLast和LinkBefore两个方法,LinkLast方法是在链表后面链接一个元素,LinkBefore方法是在链表中间插入一个元素。LinkedList的删除方法通过调用unlink方法将某个元素从链表中移除。下面是链表的插入和删除操作的核心代码。
1 //链接到指定结点之前 2 void linkBefore(E e, Node<E> succ) { 3 4 //获取给定结点的上一个结点引用 5 final Node<E> pred = succ.prev; 6 7 //创建新结点, 新结点的上一个结点引用指向给定结点的上一个结点 8 //新结点的下一个结点的引用指向给定的结点 9 final Node<E> newNode = new Node<>(pred, e, succ); 10 11 //将给定结点的上一个结点引用指向新结点 12 succ.prev = newNode; 13 14 //如果给定结点的上一个结点为空, 表明给定结点为头结点 15 if (pred == null) { 16 17 //将头结点引用指向新结点 18 first = newNode; 19 } else { 20 //否则, 将给定结点的上一个结点的下一个结点引用指向新结点 21 pred.next = newNode; 22 } 23 24 //集合元素个数加一 25 size++; 26 27 //修改次数加一 28 modCount++; 29 30 } 31 32 33 34 //卸载指定结点 35 E unlink(Node<E> x) { 36 37 //获取给定结点的元素 38 final E element = x.item; 39 40 //获取给定结点的下一个结点的引用 41 final Node<E> next = x.next; 42 43 //获取给定结点的上一个结点的引用 44 final Node<E> prev = x.prev; 45 46 //如果给定结点的上一个结点为空, 说明给定结点为头结点 47 if (prev == null) { 48 49 //将头结点引用指向给定结点的下一个结点 50 first = next; 51 } else { 52 //将上一个结点的后继结点引用指向给定结点的后继结点 53 prev.next = next; 54 //将给定结点的上一个结点置空 55 x.prev = null; 56 57 } 58 59 //如果给定结点的下一个结点为空, 说明给定结点为尾结点 60 if (next == null) { 61 62 //将尾结点引用指向给定结点的上一个结点 63 last = prev; 64 } else { 65 66 //将下一个结点的前继结点引用指向给定结点的前继结点 67 next.prev = prev; 68 x.next = null; 69 70 } 71 72 //将给定结点的元素置空 73 x.item = null; 74 75 //集合元素个数减一 76 size--; 77 //修改次数加一 78 modCount++; 79 return element; 80 81 }View Code
通过源码的分析,对链表的插入和删除的时间复杂度都是O(1),而对链表的查找和修改操作都需要遍历链表进行元素的定位,这两个操作都是调用的node(int index) 方法定位元素,如下代码演示根据下标来定位元素。
1 //根据指定位置获取结点 2 Node<E> node(int index) { 3 //如果下标在链表前半部分, 就从头开始查起 4 if (index < (size >> 1)) { 5 Node<E> x = first; 6 for (int i = 0; i < index; i++) { 7 x = x.next; 8 } 9 return x; 10 } else { 11 //如果下标在链表后半部分, 就从尾开始查起 12 Node<E> x = last; 13 for (int i = size - 1; i > index; i--) { 14 x = x.prev; 15 } 16 return x; 17 } 18 }View Code
通过下标定位时先判断是在链表的上半部还是下半部
上半部:从头开始找;
下半部:从尾开始找;
因此通过下标的查找和修改操作的时间复杂度是O(n/2),通过对双向链表的操作还可以实现单项队列,双向队列和栈的功能。
单向队列的操作的代码:
1 //获取头结点 2 public E peek() { 3 final Node<E> f = first; 4 return (f == null) ? null : f.item; 5 } 6 7 //获取头结点 8 public E element() { 9 return getFirst(); 10 } 11 12 //弹出头结点 13 public E poll() { 14 final Node<E> f = first; 15 return (f == null) ? null : unlinkFirst(f); 16 } 17 18 //移除头结点 19 public E remove() { 20 return removeFirst(); 21 } 22 23 //在队列尾部添加结点 24 public boolean offer(E e) { 25 return add(e); 26 }View Code
双向队列的操作:
1 //在头部添加 2 public boolean offerFirst(E e) { 3 addFirst(e); 4 return true; 5 } 6 7 //在尾部添加 8 public boolean offerLast(E e) { 9 addLast(e); 10 return true; 11 } 12 13 //获取头结点 14 public E peekFirst() { 15 final Node<E> f = first; 16 return (f == null) ? null : f.item; 17 } 18 19 //获取尾结点 20 public E peekLast() { 21 final Node<E> l = last; 22 return (l == null) ? null : l.item; 23 }View Code
栈操作:
1 //入栈 2 public void push(E e) { 3 addFirst(e); 4 } 5 6 //出栈 7 public E pop() { 8 return removeFirst(); 9 }View Code
对LindedList,有:
1. LinkedList是基于双向链表实现的,不论是增删改查方法还是队列和栈的实现,都可通过操作结点实现
2. LinkedList无需提前指定容量,因为基于链表操作,集合的容量随着元素的加入自动增加
3. LinkedList删除元素后集合占用的内存自动缩小,无需像ArrayList一样调用trimToSize()方法
4. LinkedList的所有方法没有进行同步,因此它也不是线程安全的,应该避免在多线程环境下使用
5. 以上分析基于JDK1.7,其他版本会有些出入,因此不能一概而论
以上内容部分借鉴于:https://blog.csdn.net/iteen/article/details/83109717
原文链接:https://www.cnblogs.com/Mr-RanX/p/11267016.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 合并有序两个单链表,合并后链表依然有序 2020-06-02
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题52. 两个链表的第一个公共节点 2020-05-22
- LeetCode 160. 相交链表 2020-05-22
- LeetCode 25. K 个一组翻转链表 2020-05-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash