Java基础笔记——链表
链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。
LinkedList类实例便代表了一个链表，它的一个实例域保存了指向链表中第一个结点的引用。
class LinkedList<Item>{
private Node first;
private class Node{
Item data;
Node next;
}
· · · · · ·
}
single linked list（单向链表）:
double linked list(双向链表)：每个node不仅包含指向下后一个结点的引用，还包含着指向前一个结点的引用。
链表的优点：
链表支持插入和删除这两种操作，并且删除/插入链表头部/尾部结点的时间复杂度通常都是常数级别 [ O(1) ]
可以动态改变大小。
链表的缺点：
不支持高效的random access（随机访问）。
由于其链式存储的特性，链表不具备良好的空间局部性，也就是说，链表是一种缓存不友好的数据结构。
链表的实现
单向链表
插入节点：
public void insert(Item item) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
itemCount++;
}
删除节点：
public Item delete() {
if (first != null) {
Item item = first.item;
first = first.next;
return item;
} else {
throw new NullPointerException("There's no Node in the linked list.");
}
双向链表
双向链表相比与单链表的优势在于它同时支持高效的正向及反向遍历，并且可以方便的在链表尾部删除结点
Java实现
public class DoubleLinkedList<Item> {
private Node first;
private Node last;
private int itemCount;
private class Node {
Node prev;
Node next;
Item item;
}
public void addFirst(Item ite m) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
if (oldFirst != null) {
oldFirst.prev = first;
}
if (itemCount == 0) {
last = first;
}
itemCount++;
}
public void addLast(Item item) {
Node oldLast = last;
last = new Node();
last.item = item;
last.prev = oldLast;
if (oldLast != null) {
oldLast.next = last;
}
if (itemCount == 0) {
first = last;
}
itemCount++;
}
public Item delFirst() {
if (first == null) {
throw new NullPointerException("No node in linked list.");
}
Item result = first.item;
first = first.next;
if (first != null) {
first.prev = null;
}
if (itemCount == 1) {
last = null;
}
itemCount--;
return result;
}
public Item delLast() {
if (last == null) {
throw new NullPointerException("No node in linked list.");
}
Item result = last.item;
last = last.prev;
if (last != null) {
last.next = null;
}
if (itemCount == 1) {
first = null;
}
itemCount--;
return result;
}
public void addBefore(Item targetItem, Item item) {
//从头开始遍历寻找目标节点
Node target = first;
if (target == null) {
throw new NullPointerException("No node in linked list");
}
while (target != null && target.item != targetItem) {
//继续向后寻找目标节点
target = target.next;
}
if (target == null) {
throw new NullPointerException("Can't find target node.");
}
//现在target为指向目标结点的引用
if (target.prev == null) {
//此时相当于在表头插入结点
addFirst(item);
} else {
Node oldPrev = target.prev;
Node newNode = new Node();
newNode.item = item;
target.prev = newNode;
newNode.next = target;
newNode.prev = oldPrev;
oldPrev.next = newNode;
itemCount++;
}
}
public void addAfter(Item targetItem, Item item) {
Node target = first;
if (target == null) {
throw new NullPointerException("No node in linked list.");
}
while (target != null && target.item != targetItem) {
target = target.next;
}
if (target == null) {
throw new NullPointerException("Can't find target node.");
}
if (target.next == null) {
addLast(item);
} else {
Node oldNext = target.next;
Node newNode = new Node();
newNode.item = item;
target.next = newNode;
newNode.prev = target;
newNode.next= oldNext;
oldNext.prev = newNode;
itemCount++;
}
}
}
注：实现链表使用的是pointer wrapper方式，这种方式的特点是prev/next指针包含在结点中，而数据由结点中的另一个指针（即item）所引用。采取这种方式，在获取结点数据时，我们需要进行double-dereferencing，而且这种方式实现的链表不是一种[局部化结构]，这意味着我们拿到链表的一个结点数据后，无法直接进行insert/delete操作。
常见面试题：
1. 输入一个链表，输出该链表中倒数第k个结点。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
//先求得链表的尺寸，赋值给size
int size = 0;
ListNode current = head;
while (current != null) {
size++;
current = current.next;
}
//获取next实例域size-k次，即可得到倒数第k个结点（从1开始计数）
for (int i = 0; i < size - k; i++) {
head = head.next;
}
return head;
}
}
2. 反转链表
public ListNode ReverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode current = head;
//原head的next node为null
ListNode prevNode = null;
ListNode newHead = null;
while (current != null) {
ListNode nextNode = current.next;
current.next = prevNode;
if (nextNode == null) {
newHead = current;
}
prevNode = current;
current = nextNode;
}
return newHead;
}
以上转载
https://www.cnblogs.com/absfree/p/5463372.html