level 6
我是😈乖宝宝
楼主
手写单链表和LinkedList
2.1单链表技能点
·认识单链表


o特点
数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。
每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。逻辑上相邻的节点物理上不必相邻。
o缺点：
1. 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，
所以相同空间内假设全存满的话顺序比链式存储更多)。
2. 按照索引查找结点时链式存储要比顺序存储慢（每个节点地址不连续、无规律，导致按照索引查询效率低下。
o优点：
1. 插入、删除灵活 (不必移动节点，只要改变节点中的指针，但是需要先定位到元素上)。
2. 有元素才会分配结点空间，不会有闲置的结点。
·添加节点
·删除节点
·带头节点的单链表
在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。
在头结点中不存储任何实质的数据对象，其 next 域指向线性表中 0 号元素所在的结点，
可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。
一个不带头结点和带头结点的单链表实现线性表的结构图如图所示。
2.2手写单链表
•定义单链表节点
【示例5】定义单链表节点
public class Node { Object data;//存储是数据 Node next;//指向下个节点的指针 public Node() { super(); } public Node(Object data) { super(); this.data = data; } public Node(Object data, Node next) { super(); this.data = data; this.next = next; } //省略setter和getter方法 public String toString() { return "Node [data=" + data + ", next=" + next + "]"; } }
•手写单链表
【示例6】手写单链表
public class SingleLinkedList implements List { //头节点 哑巴节点 不存储数据 为了方便编程 private Node head = new Node(); private int size = 0;//节点的个数 public int size() { return size; } public Object get(int i) { //i从0开始 //判断i的值是否合理 if(i<0 || i>=size){ throw new IndexOutOfBoundsException("索引越界"+i); } //顺藤摸瓜，从第一个节点开始查找 Node p = head.next;//p初始指向第一个节点（不是头节点） for(int j=0;j<i;j++){ //p指向下个节点 p=p.next; } //return p.data;//返回的不是第i个节点，而是第i个节点的data return p;//返回的是第i个节点，而不是第i个节点的data } public boolean isEmpty() { return size==0; } public void add(int i, Object e) { //i值合理性判断 if(i<0 || i>size){ throw new IndexOutOfBoundsException("索引越界"+i); } //先找到前一个(如果当前索引是0，前一个就是head) Node p = head; if(i!=0){ p = (Node)this.get(i-1); } //创建一个新节点，给data赋值 Node newNode = new Node(e); //指定新节点的下一个节点 newNode.next = p.next; //指定前一个节点的下个节点是当前新节点 p.next = newNode; //数量+1 size++; } public void add(Object e) { this.add(size, e); } public Object remove(int i) { //i值合理性判断 if(i<0 || i>=size){ throw new IndexOutOfBoundsException("索引越界"+i); } //先找到前一个(如果当前索引是0，前一个就是head) Node p = head; if(i!=0){ p = (Node)this.get(i-1); } //指向要删除的节点 Node currNode = p.next; //完成删除操作 p.next = currNode.next; currNode.next = null; currNode = null;//提示将要删除的节点变成垃圾 //数量-1 size--; return null; } public String toString() { StringBuilder builder = new StringBuilder("["); Node p = head.next;//p初始指向第一个节点（不是头节点） for(int j=0;j<size;j++){ builder.append(p.data+" "); //p指向下个节点 p=p.next; } builder.append("]"); return builder.toString(); } }
单链表添加删除查询原理
•测试单链表
【示例7】测试单链表
public class TestList { public static void main(String[] args) { java.util.ArrayList list2; //创建线性顺序表 List list = new SingleLinkedList(); //向末尾添加元素 list.add("11111"); list.add("aaaaa"); list.add("bbbbb"); list.add("33333"); list.add("22222"); list.add(3, "AAAAA"); list.remove(2); //进行各种操作验证添加 System.out.println(list.size()); System.out.println(list.isEmpty()); System.out.println(list.contains("44444")); System.out.println(list.indexOf("22222")); System.out.println(list.toString()); } }
2.3 手写LinkedList
·LinkedList底层原理
² LinkedList底层是一个双向链表；添加、删除元素效率高；按照索引查询效率低。可以两个方向查询
² 每个节点都包含了对前一个和后一个元素的引用
² LinkedList同时实现了List、Deque、Queue接口，所以可以当做线性表、队列、双端队列、栈使用
² LinkedList 是非同步的（线程不安全）
² 不存在LinkedList容量不足的问题
·定义LinkedList节点
【示例8】定义LinkedList节点
public class LinkedList implements List { /** * 静态内部类 代表LinkedList的每个节点 */ private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } @override public String toString() { return "Node{" + "item=" + item +", next=" + next +'}'; } } }
·手写LinkedList
【示例9】手写LinkedList
public class LinkedList implements List { transient int size = 0; transient Node first; transient Node last; public int size() { return size; } public Object get(int i) { return node(i).item; } public boolean isEmpty() { return size ==0; } public void add(int index, Object element) { if (index == size) linkLast(element); else linkBefore(element, node(index)); } Node node(int index) { if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } void linkBefore(Object e, Node succ) { final Node pred = succ.prev; final Node newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; } public void add(Object e) { linkLast(e); } public void linkLast(Object e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; } public String toString() { return first.toString(); } }
下面是LinkedList的add(Object)方法的实现过程
·测试LinkedList
【示例10】测试LinkedList
public class TestList { public static void main(String[] args) { //创建线性顺序表 List list = new LinkedList(); //向末尾添加元素 list.add("11111"); list.add("aaaaa"); list.add("bbbbb"); list.add("33333"); list.add("22222"); list.add(3, "AAAAA"); //进行各种操作验证添加 System.out
2020年05月20日 14点05分
1
2.1单链表技能点
·认识单链表


o特点
数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。
每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。逻辑上相邻的节点物理上不必相邻。
o缺点：
1. 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，
所以相同空间内假设全存满的话顺序比链式存储更多)。
2. 按照索引查找结点时链式存储要比顺序存储慢（每个节点地址不连续、无规律，导致按照索引查询效率低下。
o优点：
1. 插入、删除灵活 (不必移动节点，只要改变节点中的指针，但是需要先定位到元素上)。
2. 有元素才会分配结点空间，不会有闲置的结点。
·添加节点
·删除节点
·带头节点的单链表
在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。
在头结点中不存储任何实质的数据对象，其 next 域指向线性表中 0 号元素所在的结点，
可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。
一个不带头结点和带头结点的单链表实现线性表的结构图如图所示。
2.2手写单链表
•定义单链表节点
【示例5】定义单链表节点
public class Node { Object data;//存储是数据 Node next;//指向下个节点的指针 public Node() { super(); } public Node(Object data) { super(); this.data = data; } public Node(Object data, Node next) { super(); this.data = data; this.next = next; } //省略setter和getter方法 public String toString() { return "Node [data=" + data + ", next=" + next + "]"; } }
•手写单链表
【示例6】手写单链表
public class SingleLinkedList implements List { //头节点 哑巴节点 不存储数据 为了方便编程 private Node head = new Node(); private int size = 0;//节点的个数 public int size() { return size; } public Object get(int i) { //i从0开始 //判断i的值是否合理 if(i<0 || i>=size){ throw new IndexOutOfBoundsException("索引越界"+i); } //顺藤摸瓜，从第一个节点开始查找 Node p = head.next;//p初始指向第一个节点（不是头节点） for(int j=0;j<i;j++){ //p指向下个节点 p=p.next; } //return p.data;//返回的不是第i个节点，而是第i个节点的data return p;//返回的是第i个节点，而不是第i个节点的data } public boolean isEmpty() { return size==0; } public void add(int i, Object e) { //i值合理性判断 if(i<0 || i>size){ throw new IndexOutOfBoundsException("索引越界"+i); } //先找到前一个(如果当前索引是0，前一个就是head) Node p = head; if(i!=0){ p = (Node)this.get(i-1); } //创建一个新节点，给data赋值 Node newNode = new Node(e); //指定新节点的下一个节点 newNode.next = p.next; //指定前一个节点的下个节点是当前新节点 p.next = newNode; //数量+1 size++; } public void add(Object e) { this.add(size, e); } public Object remove(int i) { //i值合理性判断 if(i<0 || i>=size){ throw new IndexOutOfBoundsException("索引越界"+i); } //先找到前一个(如果当前索引是0，前一个就是head) Node p = head; if(i!=0){ p = (Node)this.get(i-1); } //指向要删除的节点 Node currNode = p.next; //完成删除操作 p.next = currNode.next; currNode.next = null; currNode = null;//提示将要删除的节点变成垃圾 //数量-1 size--; return null; } public String toString() { StringBuilder builder = new StringBuilder("["); Node p = head.next;//p初始指向第一个节点（不是头节点） for(int j=0;j<size;j++){ builder.append(p.data+" "); //p指向下个节点 p=p.next; } builder.append("]"); return builder.toString(); } }
单链表添加删除查询原理
•测试单链表
【示例7】测试单链表
public class TestList { public static void main(String[] args) { java.util.ArrayList list2; //创建线性顺序表 List list = new SingleLinkedList(); //向末尾添加元素 list.add("11111"); list.add("aaaaa"); list.add("bbbbb"); list.add("33333"); list.add("22222"); list.add(3, "AAAAA"); list.remove(2); //进行各种操作验证添加 System.out.println(list.size()); System.out.println(list.isEmpty()); System.out.println(list.contains("44444")); System.out.println(list.indexOf("22222")); System.out.println(list.toString()); } }
2.3 手写LinkedList
·LinkedList底层原理
² LinkedList底层是一个双向链表；添加、删除元素效率高；按照索引查询效率低。可以两个方向查询
² 每个节点都包含了对前一个和后一个元素的引用
² LinkedList同时实现了List、Deque、Queue接口，所以可以当做线性表、队列、双端队列、栈使用
² LinkedList 是非同步的（线程不安全）
² 不存在LinkedList容量不足的问题
·定义LinkedList节点
【示例8】定义LinkedList节点
public class LinkedList implements List { /** * 静态内部类 代表LinkedList的每个节点 */ private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } @override public String toString() { return "Node{" + "item=" + item +", next=" + next +'}'; } } }
·手写LinkedList
【示例9】手写LinkedList
public class LinkedList implements List { transient int size = 0; transient Node first; transient Node last; public int size() { return size; } public Object get(int i) { return node(i).item; } public boolean isEmpty() { return size ==0; } public void add(int index, Object element) { if (index == size) linkLast(element); else linkBefore(element, node(index)); } Node node(int index) { if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } void linkBefore(Object e, Node succ) { final Node pred = succ.prev; final Node newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; } public void add(Object e) { linkLast(e); } public void linkLast(Object e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; } public String toString() { return first.toString(); } }
下面是LinkedList的add(Object)方法的实现过程
·测试LinkedList
【示例10】测试LinkedList
public class TestList { public static void main(String[] args) { //创建线性顺序表 List list = new LinkedList(); //向末尾添加元素 list.add("11111"); list.add("aaaaa"); list.add("bbbbb"); list.add("33333"); list.add("22222"); list.add(3, "AAAAA"); //进行各种操作验证添加 System.out