数组需要一块连续的内存空间来存储,而链表不需要一块连续的内存空阿金,通过指针将一组零散的内存块串联起来,数组对内存的要求较高,如果申请一个100MB大小的数组,内存中没有连续的,足够大的存储空间时,即便内存的剩余总可用空间大于100MB,仍然会申请失败,而申请100MB大小的链表,则不会有问题单链表将内存块称为链表的结点,每个结点除了存储数据之外,还需要记录链上的下一个结点的地址,称为后继指针next循环链表循环链表与单链表的唯一区别就是尾结点,单链表的尾结点指针指向空地址,表示最后的结点,而循环链表的尾结点指针是指向链表的头结点,当处理的数据具有环形结构的特点,就适合采用循环链表,如约瑟夫问题双向链表双向链表每个结点不止有一个后继指针next指向后面的结点,还有一个前驱指针prev指向前面的结点显然,存储同样多的数据,双向链表比单链表占用更多的内存空间,但是因为保存了前驱结点和后继节点,也使双向链表在某些情况下的插入删除等操作要比单链表简单高效写链表代码的技巧利用哨兵简化实现难度针对链表的插入,删除操作,需要对插入第一个节点和删除的最后一个节点的情况进行特殊处理,解决方法是引入哨兵节点,在任何时候,不管链表是不是空,head指针都会一直指向这个哨兵节点,将这种有哨兵节点的链表称为带头链表,相反则为不带头链表哨兵模式的例子// 在数组 a 中查找 key返回 key 所在的位置 // 其中n 表示数组 a 的长度 int find(char* a, int n, char key) { // 边界条件处理如果 a 为空或者 n0说明数组中没有数据就不用 while 循环比较了 if(a null || n 0) { return -1; } int i 0; // 这里有两个比较操作in 和 a[i]key. while (i n) { if (a[i] key) { return i; } i; } return -1; } 代码二 // 在数组 a 中查找 key返回 key 所在的位置 // 其中n 表示数组 a 的长度 // 我举 2 个例子你可以拿例子走一下代码 // a {4, 2, 3, 5, 9, 6} n6 key 7 // a {4, 2, 3, 5, 9, 6} n6 key 6 int find(char* a, int n, char key) { if(a null || n 0) { return -1; } // 这里因为要将 a[n-1] 的值替换成 key所以要特殊处理这个值 if (a[n-1] key) { return n-1; } // 把 a[n-1] 的值临时保存在变量 tmp 中以便之后恢复。tmp6。 // 之所以这样做的目的是希望 find() 代码不要改变 a 数组中的内容 char tmp a[n-1]; // 把 key 的值放到 a[n-1] 中此时 a {4, 2, 3, 5, 9, 7} a[n-1] key; int i 0; // while 循环比起代码一少了 in 这个比较操作 while (a[i] ! key) { i; } // 恢复 a[n-1] 原来的值, 此时 a {4, 2, 3, 5, 9, 6} a[n-1] tmp; if (i n-1) { // 如果 i n-1 说明在 0...n-2 之间都没有 key所以返回 -1 return -1; } else { // 否则返回 i就是等于 key 值的元素的下标 return i; } }链表的实现与应用1. 单链表的实现package com.zach.geekbang.datastructure.linkedlist; /** * Author Zhangsz * Description: * Date 2019/5/16 15:06 * ClassName SinglyLinkedList */ public class SinglyLinkedList { private Node head null; public Node findByValue(int value) { Node p head; while (p ! null p.data ! value) { p p.next; } return p; } public Node findByIndex(int index) { Node p head; int pos 0; while (p ! null pos ! index) { p p.next; pos; } return p; } /** * 功能描述 * 无头结点,表头部插入,与输入的顺序相反 * * Author Zhangsz * Description: * date: 2019/5/16 * param: * param value * return: void */ public void insertToHead(int value) { Node node new Node(value, null); insertToHead(node); } public void insertToHead(Node newNode) { if (head ! null) { newNode.next head; head newNode; } this.head newNode; } /** * 功能描述 * 顺序插入,尾部插入 * * Author Zhangsz * Description: * date: 2019/5/16 * param: * param value * return: void */ public void insertToTail(int value) { Node newNode new Node(value, null); insertToTail(newNode); } private void insertToTail(Node newNode) { if (head null) { head newNode; } else { Node p head; while (p.next ! null) { p p.next; } newNode.next p.next; p.next newNode; } } public void insertAfter(Node p, int value) { Node newNode new Node(value, null); insertAfter(p, newNode); } public void insertAfter(Node p, Node newNode) { if (p null) return; newNode.next p.next; p.next newNode; } public void insertBefore(Node p, int value) { Node newNode new Node(value, null); insertBefore(p, newNode); } public void insertBefore(Node p, Node newNode) { if (p null) return; if (head p) { insertToHead(newNode); return; } Node q head; while (q ! null q.next ! p) { q q.next; } if (q null) return; newNode.next p; q.next newNode; } public void deleteByNode(Node p) { if (p null || head null) return; if (p head) { head head.next; return; } Node preNode head; while (preNode ! null preNode.next ! p) { preNode preNode.next; } if (preNode null) return; preNode.next preNode.next.next; } public void deleteByValue(int value) { if (head null) { return; } Node p head; Node q null; if (p ! null p.data ! value) { q p; p p.next; } if (p null) return; if (q null) { head head.next; } else { q.next q.next.next; } } public static class Node { private int data; private Node next; public Node(int data, Node next) { this.data data; this.next next; } public int getData() { return data; } } }2. 基于单链表LRU淘汰算法:最近最少的使用策略public class LRUBaseLinkedListT { //默认链表容量 private final static Integer DEFAULT_CAPACITY 10; //头节点 private SNode headNode; //链表长度 private Integer length; //链表容量 private Integer capacity; public LRUBaseLinkedList() { this.headNode new SNode(); this.capacity DEFAULT_CAPACITY; this.length 0; } public LRUBaseLinkedList(Integer capacity) { this.headNode new SNode(); this.capacity capacity; this.length 0; } public void add(T data) { SNode preNode findPreNodeByValue(data); //链表中存在删除原数据,并将新数据插入到链表的头部 if (preNode ! null) { deleteElemOptim(preNode); intsertElemAtBegin(data); } else { if (length this.capacity) { //删除尾结点 deleteElemAtEnd(); } intsertElemAtBegin(data); } } private void deleteElemAtEnd() { SNode temp headNode; if (temp.getNext() null) return; while (temp.getNext().getNext() ! null) { temp temp.getNext(); } SNode target temp.getNext(); temp.setNext(null); target null; length--; } private void intsertElemAtBegin(T data) { SNode next headNode.getNext(); headNode.setNext(new SNode(data,next)); length; } private void deleteElemOptim(SNode preNode) { if (preNode ! null) { SNode temp preNode.getNext(); preNode.setNext(temp.getNext()); temp null; length--; } } private SNode findPreNodeByValue(T data) { SNode node headNode; while (node.getNext() ! null) { if (data.equals(node.getNext().getElement())) { return node; } else { node node.getNext(); } } return null; } private void printAll(){ System.out.println(); SNode node headNode.getNext(); while (node ! null) { System.out.println(node.getElement(),); node node.getNext(); } System.out.println(); } public class SNodeT { private T element; private SNode next; public SNode(T element) { this.element element; } public SNode(T element, SNode next) { this.element element; this.next next; } public SNode() { this.next null; } public T getElement() { return element; } public void setElement(T element) { this.element element; } public SNode getNext() { return next; } public void setNext(SNode next) { this.next next; } } public static void main(String[] args) { LRUBaseLinkedListInteger list new LRUBaseLinkedList(); Scanner sc new Scanner(System.in); int count 0; while (count10) { int temp sc.nextInt(); list.add(temp); list.printAll(); count; } } }