鏈表 (Linked List)
-
鏈表是一種鏈?zhǔn)酱鎯?chǔ)的線性表，所有元素的內(nèi)存地址不一定是連續(xù)的
1.png - 可以辦到需要多少內(nèi)存就申請(qǐng)多少內(nèi)存菠净，避免內(nèi)存空間大量浪費(fèi)
鏈表設(shè)計(jì)
-
結(jié)構(gòu)2.png
-
接口設(shè)計(jì)3.png
- 代碼實(shí)現(xiàn)（java)
List接口
package com.jxs;
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清除所有元素
*/
void clear();
/**
* 元素的數(shù)量
* @return
*/
int size();
/**
* 是否為空
* @return
*/
boolean isEmpty();
/**
* 是否包含某個(gè)元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到尾部
* @param element
*/
void add(E element);
/**
* 獲取index位置的元素
* @param index
* @return
*/
E get(int index);
/**
* 設(shè)置index位置的元素
* @param index
* @param element
* @return 原來(lái)的元素
*/
E set(int index,E element);
/**
* 在index位置插入一個(gè)元素
* @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>{
/**
* 元素的數(shù)量
*/
protected int size;
/**
* 元素的數(shù)量
* @return
*/
public int size() {
return size;
}
/**
* 是否為空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某個(gè)元素
* @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函數(shù)調(diào)用
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.刪除鏈表中的節(jié)點(diǎn)
https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
4.png
5.png
java代碼實(shí)現(xiàn)
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
2.反轉(zhuǎn)鏈表
https://leetcode-cn.com/problems/reverse-linked-list/
6.png
- 遞歸
7.png
java代碼實(shí)現(xiàn)
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;
}
- 循環(huán)（while循環(huán)，每次把節(jié)點(diǎn)指向上一個(gè)節(jié)點(diǎn)）
java代碼實(shí)現(xiàn)
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.環(huán)形鏈表
https://leetcode-cn.com/problems/linked-list-cycle/
7.png
快慢指針西采，相當(dāng)于兩人在賽道跑步美尸，速度快的總會(huì)追上速度慢的。
java代碼實(shí)現(xiàn)
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;
}
