JDK源码阅读-------自学笔记(二十三)(java.util.LinkedList 初探 自定义讲解)
1、LinkedList简介
- (1) 底层用双向链表实现的存储
- (2) 查询效率低，频繁增删效率高，线程不安全是其主要特点
- (3) 常用单词Node/Entry表示一个节点,或称为条项,词条(形容节点的样子)
- (4) 链表由三部分组成:前一个节点,本节点保存的数据,后一个节点
2、LinkedList和Collection的关系
3、双向链表Java实现
- (1) 定义一个对象Node,在对象中定义组成节点的三部分:上一个节点、数据位置、下一个节点
- (2) 定义一个链表对象,在链表对象中操作节点对象.
-
(3) 以add方法为例子:
- 每天执行add()方法的时候,新建一个节点Node,将要添加的元素,放入到Node对象中
- 第一次添加对象的时候,链表中是空的,所以,链表的第一个节点和最后一个节点都是传入的Node
- 第二次,开始,添加的对象都存在next当中,以此类推,如图:
-
形成了类似递归的添加方式.
-
4、实战代码
- 实体类Node，建立
1 package com.synway.test.collections.version3.basesimple; 2 3 /** 4 * @author liuyangos8888 5 * @description
存储元素的实体类对象
6 */ 7 public class Node { 8 9 10 /** 11 * 上一个节点 12 */ 13 Node previous; 14 15 /** 16 * 存储数据 17 */ 18 Object elements; 19 20 21 /** 22 * 下一个节点 23 */ 24 Node next; 25 26 27 public Node() { 28 29 } 30 31 public Node(Object elements) { 32 this.elements = elements; 33 } 34 35 public Node(Node previous, Object elements, Node next) { 36 this.previous = previous; 37 this.elements = elements; 38 this.next = next; 39 } 40 41 public Node getPrevious() { 42 return previous; 43 } 44 45 public void setPrevious(Node previous) { 46 this.previous = previous; 47 } 48 49 public Object getElements() { 50 return elements; 51 } 52 53 public void setElements(Object elements) { 54 this.elements = elements; 55 } 56 57 public Node getNext() { 58 return next; 59 } 60 61 public void setNext(Node next) { 62 this.next = next; 63 } 64 } - 链表类建立
1 package com.synway.test.collections.version3.basesimple; 2 3 import com.synway.test.collections.version002.methodadd.base.son.AbstractMyCollection; 4 5 import java.util.Iterator; 6 7 /** 8 * @author liuyangos8888 9 * @description
自定义一个链表
10 */ 11 public class MyLinkedList { 12 13 /** 14 * 第一个节点 15 */ 16 private Node firstNode; 17 18 19 /** 20 * 最后一个节点 21 */ 22 private Node lastNode; 23 24 25 /** 26 * 链表大小 27 */ 28 private int size; 29 30 31 /** 32 * 添加元素 33 * 34 * @param o 传入的元素 35 */ 36 public void add(Object o) { 37 Node node = new Node(o); 38 39 40 if (firstNode == null) { 41 firstNode = node; 42 } else { 43 node.previous = lastNode; 44 node.next = null; 45 lastNode.next = node; 46 } 47 lastNode = node; 48 } 49 50 51 /** 52 * 添加元素(使用对象set值的方式,更适合java程序员理解) 53 * 54 * @param o 传入的元素 55 */ 56 public void addObject(Object o) { 57 Node node = new Node(); 58 node.setElements(o); 59 60 if (firstNode == null) { 61 firstNode = node; 62 } else { 63 node.setPrevious(lastNode); 64 node.setNext(null); 65 lastNode.setNext(node); 66 } 67 68 lastNode = node; 69 } 70 71 72 @Override 73 public String toString() { 74 StringBuilder stringBuilder = new StringBuilder(); 75 stringBuilder.append("["); 76 77 Node temp = firstNode; 78 79 while (temp != null) { 80 stringBuilder.append(temp.elements).append(","); 81 temp = temp.next; 82 } 83 84 stringBuilder.setCharAt(stringBuilder.length() - 1, ']'); 85 86 return stringBuilder.toString(); 87 } 88 89 } - 添加方法说明
一般add方法写法
1 /** 2 * 添加元素 3 * 4 * @param o 传入的元素 5 */ 6 public void add(Object o) { 7 Node node = new Node(o); 8 9 10 if (firstNode == null) { 11 firstNode = node; 12 } else { 13 node.previous = lastNode; 14 node.next = null; 15 lastNode.next = node; 16 } 17 lastNode = node; 18 }
适合java开发理解查看的写法
1 /** 2 * 添加元素(使用对象set值的方式,更适合java程序员理解) 3 * 4 * @param o 传入的元素 5 */ 6 public void addObject(Object o) { 7 Node node = new Node(); 8 node.setElements(o); 9 10 if (firstNode == null) { 11 firstNode = node; 12 } else { 13 node.setPrevious(lastNode); 14 node.setNext(null); 15 lastNode.setNext(node); 16 } 17 18 lastNode = node; 19 }
- 测试
一般add方法写法测试
1 package com.synway.test.version003; 2 3 import com.synway.test.collections.version3.basesimple.MyLinkedList; 4 5 public class TestLinkedList { 6 7 public static void main(String[] args) { 8 9 MyLinkedList myLinkedList = new MyLinkedList(); 10 myLinkedList.add("a"); 11 myLinkedList.add("b"); 12 myLinkedList.add("c"); 13 System.out.println(myLinkedList.toString()); 14 15 }
适合java开发理解查看的写法测试
1 package com.synway.test.version003; 2 3 import com.synway.test.collections.version3.basesimple.MyLinkedList; 4 5 public class TestLinkedList { 6 7 public static void main(String[] args) { 8 9 MyLinkedList myLinkedList2 = new MyLinkedList(); 10 myLinkedList2.addObject("a"); 11 myLinkedList2.addObject("b"); 12 myLinkedList2.addObject("c"); 13 myLinkedList2.addObject("e"); 14 myLinkedList2.addObject("f"); 15 System.out.println(myLinkedList2.toString()); 16 17 } 18 }
- 实体类Node，建立