1. 二维数组的内存地址是怎么样的？写出寻址公式？
  2. a[] = new int[10]; ==> loc = init_loc(初始内存地址)+index(数组的下标)*size(数据的长度)
  4. 二维=>转化一维
  5. 1 2 3
  6. 4 5 6     => 1 2 3 4 5 6 => 4的下标在二维里面是 （1 ，0） =>在一维里面是第3个。=> i*n(一维的长度)+j（在列 ）=>1*3+0=3
  8. a[i][j]: (i<n,j<m)
  9. loc=init_loc+(i*n+j)*size
  1. 链表的定义
  3. 链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。画图演示：
  5. 2.特点
  6. (1)不需要连续的内存空间。
  7. (2)有指针引用
  8. (3)三种最常见的链表结构：单链表、双向链表和循环链表
  1. 图形：
  3. 从单链表图中，可以发现，有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们一般把第一个结点叫作头结点，把最后一个结点叫作尾结点。
  4. 其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。while(p.next != null){} head 自己记录的
  6. 链表的查找、插入和删除.List => 
  7. LinkedList 
  8. AarryList
  2. 循环链表:
  5. 循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表
  1. 双向链表
  3. 单向链表只有一个方向，结点只有一个后继指针next指向后面的结点。双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？
  5. Spring AOP 注解，最新的技术，红黑树和链表查找。logn，O（n） JDK1.8 到8的才转红黑树。最适合你的。架构师
  6. B+Tree:Mysql索引 叶子节点 双向链表

image.png

image.png

代码实现：

1.单向链表：

  1. package com.linkedList;
  3. public class MyLinkedList {
  5.     private ListNode head;
  7.     private int size = 0;
  11.     //O(1)
  12.     public void insertHead(int value) {
  14.         ListNode newNode = new ListNode(value);
  16.         //将新建的节点指向原始的头
  17.         newNode.next = head;
  19.         //将新建的节点赋值给头节点
  20.         head = newNode;
  21.     }
  24.     //O(N)
  25.     //将节点插入到position的位置 0就是插入到第0个节点 1就是第1个节点
  26.     public void insertNth(int data, int position) {
  27.         if (position == 0) {
  28.             //头节点插入
  29.             insertHead(data);
  30.         } else {
  31.             ListNode currentNode = head;
  32.             for (int i = 1; i < position; i++) {
  33.                 currentNode = currentNode.next;
  34.             }
  35.             ListNode newNode = new ListNode(data);
  36.             //插入新的节点
  37.             //新的节点指向下一个节点，保证后面的节点链不会断
  38.             newNode.next = currentNode.next;
  39.             //将当前的节点指向新的节点
  40.             currentNode.next = newNode;
  41.         }
  43.     }
  47.     //O(1)
  48.     public void deleteHead() {
  49.         if (head != null) {
  50.             head = head.next;
  51.         }
  53.     }
  56.     //O(N)
  57.     public void deleteNth(int position) {
  58.         if (position == 0) {
  59.             deleteHead();
  60.         } else {
  61.             ListNode cur = head;
  62.             for (int i = 1; i < position; i++) {
  63.                 cur.next = cur;
  64.             }
  66.             //防止空指针
  67.             if (cur.next != null) {
  68.                 cur.next = cur.next.next;
  69.             }
  71.         }
  73.     }
  77.     //查找
  78.     public void print() {
  79.         ListNode cur = head;
  80.         while (cur != null) {
  81.             System.out.println(cur.value+" ");
  82.             cur = cur.next;
  83.         }
  85.     }
  90.     //O(N)
  91.     public void find(int data){
  92.         ListNode cur = head;
  93.         while (cur!=null){
  94.             if(cur.value == data){
  95.                 System.out.println("查找到元素："+cur.value);
  96.                 break;
  97.             }
  98.             cur.next = cur;
  99.         }
  101.     }
  104. }
  107. class ListNode {
  109.     public int value;//值
  111.     public ListNode next;//指针
  114.     public ListNode(int value) {
  115.         this.value = value;
  116.         this.next = null;
  117.     }
  118. }

2.双向链表

  1. package com.linkedList;
  4. //双向列表
  5. public class DoubleLinkedList {
  7.     public DNode head;//头
  9.     public DNode tail;//尾
  11.     public DoubleLinkedList() {
  12.     }
  15.     public void insertHead(int data) {
  16.         DNode newNode = new DNode(data);
  17.         if (head == null) {
  18.             tail = newNode;
  19.         } else {
  20.             head.pre = newNode;
  21.             newNode.next = head;
  22.         }
  23.         head = newNode;
  24.     }
  26.     public void insertNth(int data, int position) {
  27.         if (position == 0) {
  28.             insertHead(data);
  29.         } else {
  30.             DNode cur = head;
  31.             DNode newNode = new DNode(data);
  32.             for (int i = 1; i < position; i++) {
  33.                 cur = cur.next;
  34.             }
  35.             newNode.next = cur.next;
  36.             //防止空指针 也就是cur是最后一个节点
  37.             if (cur.next != null) {
  38.                 cur.next.pre = newNode;
  39.             }
  40.             newNode.pre = cur;
  41.             cur.next = newNode;
  42.         }
  43.     }
  45.     public void deleteHead() {
  46.         if(head == null){
  47.             return;
  48.         }
  49.         if(head.next == null){
  50.             head = null;
  51.         }else{
  52.             head.next.pre = null;
  53.         }
  54.         head = head.next;
  55.     }
  58.     public void deleteByKey(int data){
  59.         DNode cur = head;
  60.         while (cur.value!=data){
  61.             if(cur.next==null){
  62.                 System.out.println("没找到节点");
  63.                 return ;
  64.             }
  65.             cur = cur.next;
  66.         }
  68.         if(cur== head){
  69.             deleteHead();
  70.         }else {
  71.             cur.pre.next = cur.next;
  72.             if(cur == tail){
  75.             }
  76.             cur.next.pre = cur.pre;
  78.         }
  79.     }
  81. }
  83. class DNode {
  85.     public int value;
  87.     //指向前一个指针
  88.     public DNode pre;
  90.     //指向后一个指针
  91.     public DNode next;
  93.     public DNode(int value) {
  94.         this.value = value;
  95.         this.next = null;
  96.         this.pre = null;
  97.     }
  98. }

3.约瑟夫问题

  1. package com.linkedList;
  3. /**
  4.  * 约瑟夫问题：详细描述我会写在这里。
  5.  * 课后完成。
  6.  * 约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。
  7.  * 现在问你最后留下的人是谁？
  8.  * 比如N=6，M=5
  9.  * 留下的就是1
  10.  * 1 2 3 4 5 6 => 6 1 2 3 4 => 6 1 2 3 =>1 2 3 => 1 3 => 1
  11.  * */
  12. public class JosefCircleMain {
  18.     public static void main(String[] args) {
  20. //        count(6);
  21.         count2(6);
  23.     }
  25.     //
  26.     private static void count2(int k) {
  27.         //1.构造循环单列表
  28.         Node head = new Node();
  29.         Node cur = head;
  30.         for (int i = 1; i <= k; i++) {
  31.             Node tmpNode = new Node(i);
  32.             cur.next = tmpNode;
  33.             cur = cur.next;
  35.         }
  36.         cur.next = head.next;
  38.         //开始遍历
  39.         int w = 5;
  40.         Node p = cur.next;
  41.         while (p.next!=p){
  42.             //1 2 3 4 5 6
  43.             for (int i = 1; i < w-1; i++) {
  44.                 p = p.next;
  45.             }
  46.             System.out.println("remove node"+p.next.value);
  47.             p.next = p.next.next;
  48.             p = p.next;
  49.         }
  51.         System.out.println("left:"+p.value);
  53.     }
  57. }
  59. class Node{
  60.     public Node next;
  61.     public int value;
  63.     public Node(int value) {
  64.         this.value = value;
  65.     }
  67.     public Node() {
  68.     }
  69. }