公司网站免费建站怎么样,成都小程序开发公司有哪些,缙云企业网站建设,齐家网装修口碑怎么样LinkedList类
1.1LinkedList类概述
LinkedList类底层是基于双向链表结构实现的#xff0c;不同于ArrayList类和Vector类是基于数组实现的#xff1b;LinkedList类是非线程安全的#xff1b;LinkedList类元素允许为null#xff0c;允许重复元素#xff1b;LinkedList类插…
LinkedList类
1.1LinkedList类概述
LinkedList类底层是基于双向链表结构实现的不同于ArrayList类和Vector类是基于数组实现的LinkedList类是非线程安全的LinkedList类元素允许为null允许重复元素LinkedList类插入、删除效率高查询效率低LinkedList类基于链表实现的因此不存在容量不足的问题不用动态扩容双向链表有三个区域前指针域、数据域、后指针域。LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList 实现 List 接口能对它进行队列操作。LinkedList 实现 Deque 接口即能将LinkedList当作双端队列使用。LinkedList 实现了Cloneable接口即覆盖了函数clone()能克隆。LinkedList 实现java.io.Serializable接口这意味着LinkedList支持序列化能通过序列化去传输。LinkedList 是非同步的。
1.2LinkedList类的方法
与ArrayList类相似LinkedList类常见方法也有add()、get()、remove()、set()、size()等用法也类似。
Object getFirst 返回链表的第一个元素。Object getLast 返回链接列表的最后一个元素。boolean containsObject element如果元素存在于列表中则返回true。void clear 删除列表中的所有元素。
1.3LinkedList类的特点
LinkedList的底层结构为双向链表将零散的内存单元通过附加的引用关联起来体现出其顺序性相比数组的连续空间存储链表对内存的利用率更高有序插入元素的顺序和取出顺序一致可重复可以插入相同的元素元素值也允许为null插入、删除操作效率高和ArrayList恰恰相反按索引查找效率较低线程不安全没有线程锁多个线程同步进行写操作的时候可能导致数据错误使用场景不会随机访问数据更多的插入删除操作更少的查询读取操作。
链表
链表通常由一连串节点组成每个节点包含任意的实例数据data fields和一或两个用来指向上一个/或下一个节点的位置的链接links 链表Linked list是一种常见的基础数据结构是一种线性表但是并不会按线性的顺序存储数据而是在每一个节点里存到下一个节点的指针(Pointer)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点链表结构可以充分利用计算机内存空间实现灵活的内存动态管理。但是链表失去了数组随机读取的优点同时链表由于增加了结点的指针域空间开销比较大。
单向链表
普通链表也叫单链表或者单向链表Single-Linked List。单链表是链表中结构最简单的。
一个单链表的节点(Node)分为两个部分第一个部分(data)保存或者显示关于节点的信息另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
查找单向链表只可向一个方向遍历一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点一直访问到需要的位置。插入而插入一个节点对于单向链表我们只提供在链表头插入只需要将当前插入的节点设置为头节点next指向原头节点即可。删除删除一个节点我们将该节点的上一个节点的next指向该节点的下一个节点。
查找图 在表头增加节点 删除节点 2.1 单向链表的具体实现
public class SingleLinkedList {private int size;//链表节点的个数private Node head;//头节点public SingleLinkedList() {size 0;head null;}//链表的每个节点类private class Node {private Object data;//每个节点的数据private Node next;//每个节点指向下一个节点的连接public Node(Object data) {this.data data;}}//在链表头添加元素public Object addHead(Object obj) {Node newHead new Node(obj);if (size 0) {head newHead;} else {newHead.next head;head newHead;}size;return obj;}//在链表头删除元素public Object deleteHead() {Object obj head.data;head head.next;size--;return obj;}//查找指定元素找到了返回节点Node找不到返回nullpublic Node find(Object obj) {Node current head;int tempSize size;while (tempSize 0) {if (obj.equals(current.data)) {return current;} else {current current.next;}tempSize--;}return null;}//删除指定的元素删除成功返回truepublic boolean delete(Object value) {if (size 0) {return false;}Node current head;Node previous head;while (current.data ! value) {if (current.next null) {return false;} else {previous current;current current.next;}}//如果删除的节点是第一个节点if (current head) {head current.next;size--;} else {//删除的节点不是第一个节点previous.next current.next;size--;}return true;}//判断链表是否为空public boolean isEmpty() {return (size 0);}//显示节点信息public void display() {if (size 0) {Node node head;int tempSize size;if (tempSize 1) {//当前链表只有一个节点System.out.println([ node.data ]);return;}while (tempSize 0) {if (node.equals(head)) {System.out.print([ node.data -);} else if (node.next null) {System.out.print(node.data ]);} else {System.out.print(node.data -);}node node.next;tempSize--;}System.out.println();} else {//如果链表一个节点都没有直接打印[]System.out.println([]);}}
}测试
public void testSingleLinkedList(){SingleLinkedList singleList new SingleLinkedList();singleList.addHead(A);singleList.addHead(B);singleList.addHead(C);singleList.addHead(D);//打印当前链表信息singleList.display();//删除CsingleList.delete(C);singleList.display();//查找BSystem.out.println(singleList.find(B).data);
}打印结果
[D-C-B-A]
[D-B-A]
B2.2 用单向链表实现栈
栈的pop()方法和push()方法对应于链表的在头部删除元素deleteHead()以及在头部增加元素addHead()。
public class StackSingleLink {private SingleLinkedList link;public StackSingleLink() {link new SingleLinkedList();}//添加元素public void push(Object obj) {link.addHead(obj);}//移除栈顶元素public Object pop() {Object obj link.deleteHead();return obj;}//判断是否为空public boolean isEmpty() {return link.isEmpty();}//打印栈内元素信息public void display() {link.display();}
}双端链表单向引用
对于单向链表我们如果想在尾部添加一个节点那么必须从头部一直遍历到尾部找到尾节点然后在尾节点后面插入一个节点。这样操作很麻烦如果我们在设计链表的时候多个对尾节点的引用那么会简单很多。
链表的节点类保留下一节点的引用单向引用。这就是双端链表。
双端链表保留对头节点、尾节点的引用可以从尾节点插入但只能从头节点删除只能从一个方向遍历相当于单向链表多了一个对尾节点的引用。
双端链表的特点双端链表的含有对第一个节点和最后一个节点的引用。
双端链表的操作读取引用插入删除头部√√√尾部√√x 注意和后面讲的双向链表的区别
3.1 双端链表的具体实现
public class DoublePointLinkedList {private Node head;//头节点private Node tail;//尾节点private int size;//节点的个数private class Node {private Object data;private Node next;public Node(Object data) {this.data data;}}public DoublePointLinkedList() {size 0;head null;tail null;}//链表头新增节点public void addHead(Object data) {Node node new Node(data);if (size 0) {//如果链表为空那么头节点和尾节点都是该新增节点head node;tail node;size;} else {node.next head;head node;size;}}//链表尾新增节点public void addTail(Object data) {Node node new Node(data);if (size 0) {//如果链表为空那么头节点和尾节点都是该新增节点head node;tail node;size;} else {tail.next node;tail node;size;}}//删除头部节点成功返回true失败返回falsepublic boolean deleteHead() {if (size 0) {//当前链表节点数为0return false;}if (head.next null) {//当前链表节点数为1head null;tail null;} else {head head.next;}size--;return true;}//判断是否为空public boolean isEmpty() {return (size 0);}//获得链表的节点个数public int getSize() {return size;}//显示节点信息public void display() {if (size 0) {Node node head;int tempSize size;if (tempSize 1) {//当前链表只有一个节点System.out.println([ node.data ]);return;}while (tempSize 0) {if (node.equals(head)) {System.out.print([ node.data -);} else if (node.next null) {System.out.print(node.data ]);} else {System.out.print(node.data -);}node node.next;tempSize--;}System.out.println();} else {//如果链表一个节点都没有直接打印[]System.out.println([]);}}
}3.2 用双端链表实现队列
public class QueueLinkedList {private DoublePointLinkedList dp;public QueueLinkedList() {dp new DoublePointLinkedList();}public void insert(Object data) {dp.addTail(data);}public void delete() {dp.deleteHead();}public boolean isEmpty() {return dp.isEmpty();}public int getSize() {return dp.getSize();}public void display() {dp.display();}}双向链表
我们知道单向链表只能从一个方向遍历那么双向链表(Double-Linked List)它可以从两个方向遍历。 具体代码实现
public class TwoWayLinkedList {private Node head;//表示链表头private Node tail;//表示链表尾private int size;//表示链表的节点个数private class Node {private Object data;private Node next;private Node prev;public Node(Object data) {this.data data;}}public TwoWayLinkedList() {size 0;head null;tail null;}//在链表头增加节点public void addHead(Object value) {Node newNode new Node(value);if (size 0) {head newNode;tail newNode;size;} else {head.prev newNode;newNode.next head;head newNode;size;}}//在链表尾增加节点public void addTail(Object value) {Node newNode new Node(value);if (size 0) {head newNode;tail newNode;size;} else {newNode.prev tail;tail.next newNode;tail newNode;size;}}//删除链表头public Node deleteHead() {Node temp head;if (size ! 0) {head head.next;head.prev null;size--;}return temp;}//删除链表尾public Node deleteTail() {Node temp tail;if (size ! 0) {tail tail.prev;tail.next null;size--;}return temp;}//获得链表的节点个数public int getSize() {return size;}//判断链表是否为空public boolean isEmpty() {return (size 0);}//显示节点信息public void display() {if (size 0) {Node node head;int tempSize size;if (tempSize 1) {//当前链表只有一个节点System.out.println([ node.data ]);return;}while (tempSize 0) {if (node.equals(head)) {System.out.print([ node.data -);} else if (node.next null) {System.out.print(node.data ]);} else {System.out.print(node.data -);}node node.next;tempSize--;}System.out.println();} else {//如果链表一个节点都没有直接打印[]System.out.println([]);}}
}有序链表
前面的链表实现插入数据都是无序的无序链表最大特点就是在头部或尾部增加新节点。在有些应用中需要链表中的数据有序。
有序链表递增递减或者其他满足一定条件的规则插入数据时从头结点开始遍历每个节点在满足规则的地方插入新节点。
在有序链表中数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度因为元素不需要移动另外链表可以扩展到全部有效的使用内存而数组只能局限于一个固定的大小中。
public class OrderLinkedList {private Node head;private class Node {private int data;private Node next;public Node(int data) {this.data data;}}public OrderLinkedList() {head null;}//插入节点并按照从小打到的顺序排列public void insert(int value) {Node node new Node(value);Node pre null;Node current head;while (current ! null value current.data) {pre current;current current.next;}if (pre null) {head node;head.next current;} else {pre.next node;node.next current;}}//删除头节点public void deleteHead() {head head.next;}public void display() {Node current head;while (current ! null) {System.out.print(current.data );current current.next;}System.out.println();}
}在有序链表中插入和删除某一项最多需要O(N)次比较平均需要O(N/2)次因为必须沿着链表上一步一步走才能找到正确的插入位置然而可以最快速度删除最值因为只需要删除表头即可如果一个应用需要频繁的存取最小值且不需要快速的插入那么有序链表是一个比较好的选择方案。比如优先级队列可以使用有序链表来实现。
5.1 有序链表和无序数组组合排序
比如有一个无序数组需要排序解冒泡排序、选择排序、插入排序这三种简单的排序时需要的时间级别都是O(N^2^)。
现在我们讲解了有序链表之后对于一个无序数组我们先将数组元素取出一个一个的插入到有序链表中然后将他们从有序链表中一个一个删除重新放入数组那么数组就会排好序了。
和插入排序一样如果插入了N个新数据那么进行大概N^2^/4次比较。但是相对于插入排序每个元素只进行了两次排序一次从数组到链表一次从链表到数组大概需要2*N次移动而插入排序则需要N^2^次移动
效率肯定是比前面讲的简单排序要高但是缺点就是需要开辟差不多两倍的空间而且数组和链表必须在内存中同时存在如果有现成的链表可以用那么这种方法还是挺好的。
总结
上面我们讲了各种链表每个链表都包括一个LinkedList对象和许多Node对象LinkedList对象通常包含头和尾节点的引用分别指向链表的第一个节点和最后一个节点。
而每个节点对象通常包含数据部分data以及对上一个节点的引用prev和下一个节点的引用next只有下一个节点的引用称为单向链表两个都有的称为双向链表。
next值为null则说明是链表的结尾如果想找到某个节点我们必须从第一个节点开始遍历不断通过next找到下一个节点直到找到所需要的。
栈和队列都是ADT可以用数组来实现也可以用链表实现。
