【数据结构】每天五分钟，快速入门数据结构（二）—

【数据结构】每天五分钟，快速入门数据结构（二）——链表

一构建一个单向链表

二特点

三时间复杂度

四相关算法

1.判断链表是否成环及成环位置

2.链表反转

五 Java中的LinkedList 类

1.使用

2.LinkedList 方法

一构建一个单向链表

// 设计链表结构class ListNode {int val;ListNode next;ListNode(){}ListNode(int val) {this.val=val;}
}
// 初始化
class MyLinkedList {//size存储链表元素的个数int size;//虚拟头结点ListNode head;
//初始化链表public MyLinkedList() {size = 0;head = new ListNode(0);}
//获取第index个节点的数值public int get(int index) {if (index < 0 || index >= size) {return -1;}ListNode currentNode = head;for (int i = 0; i <= index; i++) {currentNode = currentNode.next;}return currentNode.val;}
//在链表最前面插入一个节点public void addAtHead(int val) {addAtIndex(0, val);}
//在链表的最后插入一个节点public void addAtTail(int val) {addAtIndex(size, val);}
// 在第 index 个节点之前插入一个新节点public void addAtIndex(int index, int val) {if (index > size) {return;}if (index < 0) {index = 0;}size++;ListNode pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}ListNode toAdd = new ListNode(val);toAdd.next = pred.next;pred.next = toAdd;}
//删除第index个节点public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;if (index == 0) {head = head.next;return;}ListNode pred = head;for (int i = 0; i < index ; i++) {pred = pred.next;}pred.next = pred.next.next;}
}

二特点

长度无限
适合任意位置插入和删除频繁的场景
物理上可以不连续

三时间复杂度

访问、插入、删除的时间复杂度均为O(n）

在头部插入元素的时间复杂度为O(1）

四相关算法

1.判断链表是否成环及成环位置

public ListNode detectCycle(ListNode head) {// 判断是否成环：快慢指针相遇ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 有环ListNode index1 = fast; // 相遇节点ListNode index2 = head; // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口while (index1 != index2) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;}

2.链表反转

 public ListNode reverseList(ListNode head) {ListNode cur = new ListNode();ListNode pre = new ListNode();cur = head;pre= null; while(cur != null ) {ListNode temp = new ListNode();temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}

五 Java中的LinkedList 类

LinkedList 继承了 AbstractSequentialList 类。

LinkedList 实现了 Queue 接口，可作为队列使用。

LinkedList 实现了 List 接口，可进行列表的相关操作。

LinkedList 实现了 Deque 接口，可作为队列使用。

LinkedList 实现了 Cloneable 接口，可实现克隆。

LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

1.使用

LinkedList<String> sites = new LinkedList<String>(); // 创建链表
sites.add("Google"); // 添加元素
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
System.out.println(sites); // 打印输出链表中的元素
sites.addFirst("Wiki"); // 在链表头部添加元素
sites.addLast("Wiki");// 在链表尾部添加元素
sites.removeFirst();// 在链表头部删除元素
sites.removeLast();// 删除链表尾部元素
System.out.println(sites.getFirst());// 获取链表首个元素
System.out.println(sites.getLast());// 获取链表最后一个元素
sites.get(i)// 获取任意位置元素