链表 (Linked List)
-
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
1.png - 可以办到需要多少内存就申请多少内存，避免内存空间大量浪费
链表设计
-
结构2.png
-
接口设计3.png
- 代码实现（java)
List接口
package com.jxs;
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清除所有元素
*/
void clear();
/**
* 元素的数量
* @return
*/
int size();
/**
* 是否为空
* @return
*/
boolean isEmpty();
/**
* 是否包含某个元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到尾部
* @param element
*/
void add(E element);
/**
* 获取index位置的元素
* @param index
* @return
*/
E get(int index);
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素
*/
E set(int index,E element);
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
void add(int index,E element);
/**
* 删除index位置的元素
* @param index
* @return
*/
E remove(int index);
/**
* 查看元素的索引
* @param element
* @return
*/
int indexOf(E element);
}
AbstractList类
package com.jxs;
public abstract class AbstractList<E> implements List<E>{
/**
* 元素的数量
*/
protected int size;
/**
* 元素的数量
* @return
*/
public int size() {
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if(index <0 || index >= size) {
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if(index <0 || index > size) {
outOfBounds(index);
}
}
}
LinkedList类
package com.jxs;
public class LinkedList<E> extends AbstractList<E>{
private Node<E> first;
private static class Node<E>{
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if(index == 0) {
first = new Node<>(element, first);
}else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
if(index == 0) {
first = first.next;
}else {
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
@Override
public int indexOf(E element) {
if(element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if(node.element == null) return i;
node = node.next;
}
}else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if(element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if(i != 0) {
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}
}
Main函数调用
package com.jxs;
public class Main {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
list.add(20);
list.add(0, 10);
list.add(30);
list.add(list.size(), 40);
list.remove(1);
System.out.println(list);
}
}
lettcode
1.删除链表中的节点
https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
4.png
5.png
java代码实现
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
2.反转链表
https://leetcode-cn.com/problems/reverse-linked-list/
6.png
- 递归
7.png
java代码实现
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
- 循环（while循环，每次把节点指向上一个节点）
java代码实现
public ListNode reverseList2(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = null;
while (head != null) {
ListNode tmp = head.next;
head.next = newHead;
newHead = head;
head = tmp;
}
return newHead;
}
3.环形链表
https://leetcode-cn.com/problems/linked-list-cycle/
7.png
快慢指针，相当于两人在赛道跑步，速度快的总会追上速度慢的。
java代码实现
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
