数据结构-链表
链表特点
- 链表是一种用于存储数据集合的数据结构
- 相邻元素之间通过指针连接
- 最后一个元素的后继指针值为 NULL
- 链表的空间能够按需分配
- 没有内存空间的浪费
- 链表的长度可以增加或缩小
链表抽象数据类型操作
- 插入
- 删除
- 删除链表
- 链表长度
- 查找
链表特点
- 优点：可以常数时间内动态分配储存空间
- 缺点：储存和查找数据开销大
单向链表
- 特点：链表通常指单向链表，包含多个结点，每个结点有一个指向后继元素的 next 指针，表中最后一个结点的 next 指针值为 NULL，表示链表的结束。
单向列表的实现
public class ListNode { private Object data; private ListNode nextNode; public ListNode(Object data) { this.data = data; this.nextNode = null; } public void setNext(ListNode node) { nextNode = node; } public ListNode getNext() { return nextNode; } public void setData(Object d) { this.data = d; } public Object getData() { return data; } /*** * 链表的遍历 * @return 链表的长度 */ public int getListNodeLength() { int length = 0; ListNode tempNode = this; while (tempNode != null) { length++; tempNode = tempNode.getNext(); } return length; } public ListNode insert(ListNode nodeToInsert) { if (this == null) { return nodeToInsert; } else { ListNode temNode = this; while (temNode.getNext() != null) { temNode = temNode.getNext(); } temNode.setNext(nodeToInsert); return this; } } /*** * 在链表中插入结点，分为开头，中间，或者结尾 * @param nodeToInsert： 插入的结点 * @param position：位置 * @return 插入以后的链表 */ ListNode insertInLinkedList(ListNode nodeToInsert, int position) { if (this == null) { return nodeToInsert; } int size = getListNodeLength(); if (position > size + 1 || position < 1) { throw new PositionInvalidException("Position of node to insert is invalid ,The valid inputs are 1 to " + (size + 1)); } if (position == 1) { //在链表开头插入结点 nodeToInsert.setNext(this); return nodeToInsert; } else { //在链表中间或者结尾插入结点，需要得到插入位置的前一个位置的结点，同时拿到插入位置的结点，把要插入的结点的下一个结点指向当前位置的结点，前一个位置的结点的下一个结点指向要插入的结点，完成结点的插入操作。 ListNode tempNode = this; int count = 1; while (count < position - 1) { tempNode = tempNode.getNext(); count++; } ListNode currentNode = tempNode.getNext(); nodeToInsert.setNext(currentNode); tempNode.setNext(nodeToInsert); } return this; } /*** * 删除节点 * @param deleteNode:需要删除的节点 * @return */ public ListNode deleteNode(ListNode deleteNode) { ListNode listNode = this; Object data = deleteNode.getData(); if (listNode == null) { throw new NullPointerException("listNode is empty"); } ListNode tempNode = listNode; ListNode previousNode = null; while (tempNode != null) { if (tempNode.getData().equals(data)) { if (previousNode == null) { listNode = tempNode.getNext(); tempNode = null; } else { previousNode.setNext(tempNode.getNext()); } return listNode; } previousNode = tempNode; tempNode = tempNode.getNext(); } throw new NodeNotFoundException("This Node is not found in LinkedList"); } /** * 删除链表指定位置的结点,分为从开头删除，中间和结尾删除 * * @param headNode：链表 * @param position：删除结点的位置 * @return 删除以后的链表 */ ListNode deleteNodeFromLinkedList(ListNode headNode, int position) { int length = getListNodeLength(); if (position < 1 || position > length) { throw new PositionInvalidException("position is out of listNode"); } if (position == 1) { //删除位置在链表开头 ListNode tempNode = headNode.getNext(); headNode = null; return tempNode; } else { //删除位置在链表中间或者结尾 ListNode tempNode = headNode; int count = 1; while (count < position) { tempNode = tempNode.getNext(); count++; } ListNode currentNode = tempNode.getNext(); tempNode.setNext(currentNode.getNext()); currentNode = null; return tempNode; } } /*** * 删除单向链表 * @param headNode：链表 */ void deleteLinkedList(ListNode headNode) { ListNode auxilary, iterator = headNode; while (iterator != null) { auxilary = iterator.getNext(); iterator = null; iterator = auxilary; } } /*** * 打印单链表 * @return */ @Override public String toString() { StringBuilder sb = new StringBuilder(); if (this != null) { sb.append("ListNode:(" + this.getListNodeLength() + "){ \n"); int node = 0; ListNode temp = this; while (temp != null) { node++; sb.append(" nodeNumber:" + node + ",nodeData:" + temp.getData() + "\n"); temp = temp.getNext(); } sb.append(" }"); } return sb.toString(); } }
双向链表
- 特点
- 比单向列表多一个前驱结点指针
- 插入和删除更加费时
- 添加一个指针，需要额外的空间开销
实现
public class DLLNode { private Object data; private DLLNode next; private DLLNode previous; public DLLNode(Object data) { this.data = data; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public DLLNode getNext() { return next; } public void setNext(DLLNode next) { this.next = next; } public DLLNode getPrevious() { return previous; } public void setPrevious(DLLNode previous) { this.previous = previous; } /*** * 获取双向链表的长度 * @param headNode：双向链表 * @return */ public int getDLLNodeLength(DLLNode headNode) { DLLNode nextNode = headNode; int length = 0; while (nextNode.getNext() != null) { nextNode = nextNode.getNext(); length++; } return length; } /*** * 双向链表插入 * @param headNode：双向链表 * @param nodeToInsert：待插入结点 * @param position：位置 * @return 插入后的双向链表 */ public DLLNode insert(DLLNode headNode, DLLNode nodeToInsert, int position) { if (headNode == null) { return nodeToInsert; } int length = getDLLNodeLength(headNode); if (position > length + 1 || position < 1) { System.out.println("Position of nodeToInsert is invalid ," + "The valid inputs are 1 to " + (length + 1)); return headNode; } if (position == 1) { //在链表开头插入 headNode.setPrevious(nodeToInsert); nodeToInsert.setNext(headNode); nodeToInsert.setPrevious(null); return nodeToInsert; } else { // 在链表中间或者尾部插入 DLLNode tempNode = headNode; int count = 1; while (count < length - 1) { tempNode = tempNode.getNext(); count++; } DLLNode currentNode = tempNode.getNext(); nodeToInsert.setNext(currentNode); if (currentNode != null) { currentNode.setPrevious(nodeToInsert); } tempNode.setNext(nodeToInsert); nodeToInsert.setPrevious(tempNode); } return headNode; } public DLLNode delete(DLLNode headNode, int position) { int size = getDLLNodeLength(headNode); if (position > size || position < 1) { System.out.println("Position of node to delete is invalid , The valid inputs are 1 to " + (size + 1)); return headNode; } if (position == 1) { //删除双向链表的第一个位置 DLLNode tempNode = headNode.getNext(); tempNode.setPrevious(null); headNode = null; return tempNode; } else { //删除双向链表的位置在中间或者最后 DLLNode previousNode = headNode; int count = 1; while (count < position - 1) { previousNode = previousNode.getNext(); count++; } DLLNode currentNode = previousNode.getNext(); DLLNode laterNode = currentNode.getNext(); previousNode.setNext(laterNode); if (laterNode != null) laterNode.setPrevious(previousNode); currentNode = null; } return headNode; } }
循环列表
- 特点
- 没有结束标志
- 最后一个结点的 next 指向头结点
实现
public class CLLNode { private Object data; private CLLNode next; public Object getData() { return data; } public void setData(Object data) { this.data = data; } public CLLNode getNext() { return next; } public void setNext(CLLNode next) { this.next = next; } /*** * 遍历循环链表 * @param headNode * @return:链表的长度 */ public int circularListLength(CLLNode headNode) { int length = 0; CLLNode currentNode = headNode; while (currentNode != null) { length++; currentNode = currentNode.getNext(); if (currentNode == headNode) { break; } } return length; } /*** * 在循环列表最后插入一个结点 * @param headNode * @param nodeToInsert * @return */ public CLLNode insertAtEndInCLLNode(CLLNode headNode, CLLNode nodeToInsert) { nodeToInsert.setNext(nodeToInsert); if (headNode == null) { return nodeToInsert; } CLLNode currentNode = headNode; while (currentNode.getNext() != headNode) { currentNode.setNext(currentNode.getNext()); } currentNode.setNext(nodeToInsert); nodeToInsert.setNext(headNode); return headNode; } /*** * 在循环列表的开始位置插入节点 * @param headNode * @param nodeToInsert * @return */ public CLLNode insertAtBeginInCLLNode(CLLNode headNode, CLLNode nodeToInsert) { nodeToInsert.setNext(nodeToInsert); if (headNode == null) { return nodeToInsert; } CLLNode currentNode = headNode; while (currentNode.getNext() != headNode) { currentNode.setNext(currentNode.getNext()); } nodeToInsert.setNext(headNode); currentNode.setNext(nodeToInsert); return nodeToInsert; } /*** * 删除循环列表的最后一个节点 * @param headNode * @return */ public CLLNode deleteLastNodeFromCLLNode(CLLNode headNode) { if (headNode == null) { return null; } CLLNode tempNode = headNode; CLLNode currentNode = headNode; while (currentNode.getNext() != headNode) { tempNode = currentNode; currentNode = currentNode.getNext(); } tempNode.setNext(headNode); currentNode = null; return headNode; } /*** * 删除循环列表的头结点 * @param headNode * @return */ public CLLNode deleteFrontNodeFormCLLNode(CLLNode headNode) { if (headNode == null) { return null; } CLLNode currentNode = headNode; while (currentNode.getNext() != headNode) { currentNode = currentNode.getNext(); } CLLNode secondNode = headNode.getNext(); currentNode.setNext(secondNode); return secondNode; } }