赞
踩
与ArrayList类相似,LinkedList类常见方法也有add()、get()、remove()、set()、size()等,用法也类似。
链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields
)和一或两个用来指向上一个/或下一个节点的位置的链接(links
)
链表(Linked list
)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer
)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
普通链表,也叫单链表或者单向链表(Single-Linked List)。单链表是链表中结构最简单的。
一个单链表的节点(Node
)分为两个部分,第一个部分(data
)保存或者显示关于节点的信息,另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
查找图:
在表头增加节点:
删除节点:
- 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,找不到返回null
- public 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;
- }
-
- //删除指定的元素,删除成功返回true
- public 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();
- //删除C
- singleList.delete("C");
- singleList.display();
- //查找B
- System.out.println(singleList.find("B").data);
- }
打印结果:
- [D->C->B->A]
- [D->B->A]
- B
栈的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 |
注意和后面讲的双向链表的区别!!!
- 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,失败返回false
- public boolean deleteHead() {
- if (size == 0) {//当前链表节点数为0
- return false;
- }
- if (head.next == null) {//当前链表节点数为1
- head = 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("[]");
- }
- }
- }
- 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)
次,因为必须沿着链表上一步一步走才能找到正确的插入位置,然而可以最快速度删除最值,因为只需要删除表头即可,如果一个应用需要频繁的存取最小值,且不需要快速的插入,那么有序链表是一个比较好的选择方案。比如优先级队列可以使用有序链表来实现。
比如有一个无序数组需要排序,解冒泡排序、选择排序、插入排序这三种简单的排序时,需要的时间级别都是O(N^2^)
。
现在我们讲解了有序链表之后,对于一个无序数组,我们先将数组元素取出,一个一个的插入到有序链表中,然后将他们从有序链表中一个一个删除,重新放入数组,那么数组就会排好序了。
和插入排序一样,如果插入了N个新数据,那么进行大概N^2^/4
次比较。但是相对于插入排序,每个元素只进行了两次排序,一次从数组到链表,一次从链表到数组,大概需要2*N
次移动,而插入排序则需要N^2^
次移动,
效率肯定是比前面讲的简单排序要高,但是缺点就是需要开辟差不多两倍的空间,而且数组和链表必须在内存中同时存在,如果有现成的链表可以用,那么这种方法还是挺好的。
上面我们讲了各种链表,每个链表都包括一个LinkedList
对象和许多Node
对象,LinkedList
对象通常包含头和尾节点的引用,分别指向链表的第一个节点和最后一个节点。
而每个节点对象通常包含数据部分data
,以及对上一个节点的引用prev
和下一个节点的引用next
,只有下一个节点的引用称为单向链表,两个都有的称为双向链表。
next
值为null
则说明是链表的结尾,如果想找到某个节点,我们必须从第一个节点开始遍历,不断通过next
找到下一个节点,直到找到所需要的。
栈和队列都是ADT
,可以用数组来实现,也可以用链表实现。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。