顺序表List

一，线性表

元素/数据在线性表当中都有唯一的前驱和后继

二，顺序表

顺序表在逻辑结构上是连续的，在物理结构上是连续的

顺序表的底层逻辑是数组来实现的

三，接口的实现

public class MyArrayList implements IList{ public int[] elem; public int usedSize; public static final int DEFAULT_CAPACITY = 10; public MyArrayList(){ // array = new int[10]; elem = new int[DEFAULT_CAPACITY]; } public MyArrayList(int initCapacity){ elem = new int[initCapacity]; } public boolean isFull(){ return usedSize == elem.length; } /** * 把数据data放在顺序表中，默认是放在顺序表最后一个位置 * @param data */ @Override public void add(int data) { if(isFull()){ //二倍扩容 grow(); } elem[usedSize] = data; usedSize++; //写到这不够严谨，还没有考虑满了的情况 } private void grow(){ elem = Arrays.copyOf(elem,2*elem.length); } private void grow(int growNum){ elem = Arrays.copyOf(elem,growNum*elem.length); } @Override public void add(int pos, int data) { checkPos(pos); if(isFull()){ grow(); } for (int i = usedSize-1; i >= pos; i--) { elem[i+1] = elem[i]; } elem[pos] = data; usedSize++; } private void checkPos(int pos){ if(pos < 0 || pos > usedSize){ throw new PosOutOfBoundsException("添加元素时pos位置不合法" + pos); } } @Override public boolean contains(int toFind) { for (int i = 0; i < usedSize; i++) { if(elem[i] == toFind){ return true; } } return false; } @Override public int indexOf(int toFind) { for (int i = 0; i < usedSize; i++) { if(elem[i] == toFind){ return i; } } return -1; } @Override public int get(int pos) { if(isEmpty()){ throw new ListEmptyException("获取元素时，顺序表为空..."); } checkPosByGetOrSet(pos); return elem[pos]; } private void checkPosByGetOrSet(int pos){ if(pos < 0 || pos >= usedSize){ throw new PosOutOfBoundsException("添加元素时pos位置不合法" + pos); } } @Override public void set(int pos, int value) { checkPosByGetOrSet(pos); elem[pos] = value; } @Override public void remove(int toRemove) { int index = indexOf(toRemove); if(index == -1){ System.out.println("没有你要删除的数据"); return; } for (int i = index; i < usedSize-1; i++) { elem[i] = elem[i+1]; } //如果是引用类型则还需要加一句 //elem[i] = null; //usedSize--; } @Override public int size() { return usedSize; } @Override public void clear() { //如果是引用类型则需要一个一个地置为null usedSize = 0; } @Override public void display() { for (int i = 0; i < usedSize; i++) { System.out.print(elem[i] + " "); } System.out.println(); } @Override public boolean isEmpty() { return usedSize == 0; } }

四，ArrayList

1) ArratList是用泛型方法实现的，使用时必须要先实例化

2）ArratList实现了RandomAccess接口，表明ArratList支持随机访问

3）ArratList实现了Cloneable接口，表明ArratList是可以clone的

4）ArratList实现了Serializable接口，表明ArratList是支持序列化的

5）和vector不同，ArratList不是线程安全，在单线程下可以使用，在多线程中可以选择vector或者CopyOnWriteArratList

6）ArratList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

public static void main(String[] args) { ArrayList<Integer> arrayList = new ArrayList(); arrayList.add(1); arrayList.add(2); arrayList.add(3); arrayList.add(4); arrayList.add(5); System.out.println(arrayList); List<Integer> list = arrayList.subList(1,4); System.out.println(list); System.out.println("======"); list.set(0,22); System.out.println(list); System.out.println(arrayList); }

在这个代码中list进行修改时，arrayList当中的数据也被修改，这是因为list存储的是array ListsubList方法后的地址

五，ArrayList的具体使用

5.1 ArrayList的遍历方式

//方法一，直接打印 System.out.println(arrayList); System.out.println(); //方法二，for循环遍历打印 for (int i = 0; i < arrayList.size(); i++) { System.out.print(arrayList.get(i) + " "); } System.out.println(); //方法三，foreach遍历 for(Integer x : arrayList){ System.out.print(x + " "); } System.out.println(); //方法四，迭代器遍历 Iterator<Integer> it = arrayList.iterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); System.out.println("===================="); ListIterator<Integer> lit = arrayList.listIterator(); while(lit.hasNext()){ System.out.println(it.next()+" "); } System.out.println(); System.out.println("=====================");

实现了Iterable接口的类都可以使用迭代器进行遍历，例如LIst，Set等等，但如果是Map这种没有实现iterable接口的则不可以直接用迭代器进行遍历，但是可以将Map当中的数据类型转换为List或别的实现了Iterator接口的来用迭代器进行遍历

六，ArrayList的应用

1，简单的洗牌算法

public class Card { public String suit; public int rank; public Card(String suit, int rank) { this.suit = suit; this.rank = rank; } @Override public String toString() { return "Card{" + "suit='" + suit + '\'' + ", rank=" + rank + '}'; } } public class CardGame { public static final String[] suits = {"♣","♦","♥","♠"}; public List<Card> buyCard(){ List<Card> cardList = new ArrayList<>(); for (int i = 0; i < 4; i++) { for (int j = 0; j < 13; j++) { String suit = suits[i]; int rank = j; Card card = new Card(suit,rank); cardList.add(card); } } return cardList; } public void swap(List<Card> cardList,int i,int j){ Card tmp = cardList.get(i); cardList.set(i,cardList.get(j)); cardList.set(j,tmp); } public void shuffle(List<Card> cardList){ Random random = new Random(); for (int i = cardList.size()-1; i > 0; i--) { int index = random.nextInt(i); swap(cardList,i,index); } } }

七，链表

7.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的

链表是一个一个的节点/结点组成的

分类： 单向 双向

带头 不带头

循环 不循环

7.2 链表的实现

public class MySingleList { //节点类 static class ListNode{ public int val; public ListNode next; public ListNode(int val){ this.val = val; } } public ListNode head; public void createList(){ ListNode node1 = new ListNode(12); ListNode node2 = new ListNode(23); ListNode node3 = new ListNode(44); ListNode node4 = new ListNode(55); ListNode node5 = new ListNode(166); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; this.head = node1; } public void show(){ //如果想让head停留在最后一个结点上，则判断条件用head.next != null //如果想要遍历完所有的节点则判断条件用head != null // while(head != null){ // System.out.print(head.val + " "); // head = head.next; // } // System.out.println(); //以上方法会让head丢失 ListNode cur = head; while(cur != null){ System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } public int size(){ int count = 0; ListNode cur = head; while(cur != null){ count++; cur = cur.next; } return count; } public boolean contains(int key){ ListNode cur = head; while(cur != null){ if(cur.val == key){ return true; } cur = cur.next; } return false; } //头插 //时间复杂度为O（1） //链表的插入需要先绑定后面的节点 public void addFirst(int data){ ListNode node = new ListNode(data); node.next = head; head = node; } //尾插 public void addLast(int data){ ListNode node = new ListNode(data); if(head == null){ node = head; return; } ListNode cur = head; while(cur.next != null){ cur = cur.next; } cur.next = node; } public void addIndex(int index,int data){ int size = size(); if(index < 0 || index > size){ return; } if(index == 0){ addFirst(data); return; } if(index == size){ addLast(data); return; } ListNode cur = searchIndex(index); if(cur == null) { return; } ListNode node = new ListNode(data); node.next = cur.next; cur.next = node; } //找到index位置的前一个节点 private ListNode searchIndex(int index){ int len = size(); if(index < 0 || index > len){ return null; } ListNode cur = head; int count = 0; while(count != index-1){ cur = cur.next; count++; } return cur; } //查找关键字Key的前驱节点，找到返回地址，找不到返回null private ListNode findNode(int key){ if(head == null){ return null; } ListNode prev = head; while(prev.next != null){ if(prev.next.val == key){ return prev; } prev = prev.next; } return null; } //删除key第一次出现时的节点 public void remove(int key){ if(head == null){ return; } if(head.val == key){ head = head.next; return; } ListNode prev = findNode(key); if(prev == null){ return; } ListNode del = prev.next; prev.next = del.next; } //删除所有值为key的节点 public void removeAllKey(int key){ if(head == null){ return; } ListNode prev = head; ListNode cur = head.next; while(cur != null){ if(cur.val == key){ prev.next = cur.next; cur = cur.next; }else{ prev = cur; cur = cur.next; } } if(head.val == key){ head = head.next; } } public void clear(){ this.head = null; } }

7.3 链表OJ

7.3.1 反转链表

方法一，递归

注意：每一次递归返回的head是不一样的

class Solution { public ListNode reverseList(ListNode head) { if(head == null){ return head; } if(head.next == null){ return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } }

方法二，循环

不停地循环头插

class Solution { public ListNode reverseList(ListNode head) { if(head == null){ return head; } ListNode cur = head.next; head.next = null; while(cur != null){ ListNode curN = cur.next; cur.next = head; head = cur; cur = curN; } return head; } }

7.3.2 给定⼀个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回二个中间结点

使用快慢双指针

快慢指针的原理：fast的速度是slow的速度的两倍，当fast到达终点的时候，slow正好在一半的路程上

public ListNode middleNode(ListNode head) { if(head == null){ return head; } if(head.next == null){ return head; } ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; }

其中while循环当中的判断条件不可以交换顺序，否则会出现空指针异常，可能会出现fast为null但是使用了fast.next

7.3.3 输入一个链表，输出该链表中倒数第k个结点

方法一，用cur走len-k步

方法二，让fast先走k-1步，然后fast和slow同时走

当fast走到最后一个节点时，使得倒数第k个节点为slow则fast和slow相差k-1的距离

public int kthToLast(ListNode head, int k) { if(k < 0){ return -1; } ListNode fast = head; ListNode slow = head; int count = 0; while(count != k-1){ fast = fast.next; count++; } while(fast.next != null){ fast = fast.next; slow = slow.next; } return slow.val; } }

7.3.4 将两个有序链表合并为⼀个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode newH = new ListNode(); ListNode tmp = newH; while(list1 != null && list2 != null){ if(list1.val < list2.val){ tmp.next = list1; list1 = list1.next; }else{ tmp.next = list2; list2 = list2.next; } tmp = tmp.next; } if(list1 != null){ tmp.next = list1; } if(list2 != null){ tmp.next = list2; } return newH.next; }

7.3.5 编写代码，以给定值x为基准将链表分割成两部分，所有⼩于x的结点排在⼤于或等于x的结点之前

方法： 1，定义cur遍历原来的链表的每个节点

2，小于x的放到第一个链表当中

3，大于等于x的放到第二个链表当中（尾插）

4，把第一个链表和第二个链表串起来，返回第一个链表的地址就可以了

public ListNode partition(ListNode pHead, int x) { // write code here ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = pHead; while(cur != null){ if(cur.val < x){ if(bs == null){ bs = be = cur; }else{ be.next = cur; be = be.next; } }else{ if(as == null){ as = ae = cur; }else{ ae.next = cur; ae = ae.next; } } cur = cur.next; } if(bs == null){ return as; } be.next = as; if(as != null){ ae.next = null; } return bs; }

7.3.6判断是否为回文链表

快慢指针＋逆转链表

public boolean chkPalindrome(ListNode A) { // write code here ListNode fast = A; ListNode slow = A; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } ListNode cur = slow.next; while(cur != null){ ListNode curN = cur.next; cur.next = slow; slow = cur; cur = curN; } while(slow != A){ if(A.val != slow.val){ return false; } if(A.next == slow){ return true; } A = A.next; slow = slow.next; } return true; }

7.3.7 相交链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = 0; int lenB = 0; //pl为较长的链表，ps为较短的链表 ListNode pl = headA; ListNode ps = headB; while(pl != null){ lenA++; pl = pl.next; } pl = headA; while(ps != null){ lenB++; ps = ps.next; } ps = headB; int len = lenA - lenB; if(len < 0){ pl = headB; ps = headA; len = lenB-lenA; } while(len != 0){ pl = pl.next; len--; } while(ps != pl){ pl = pl.next; ps = ps.next; } if(pl == null){ return null; } return pl; }

7.3.8 环形链表

题目：判断一个链表中到底有没有环

快慢指针在环中一定会相遇（一个走两步，一个走一步）

public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ return true; } } return false; }

八，双向链表

8.1 双向链表的实现

public class MyLinkedList { static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } } //标记头 public ListNode head; //标记尾 public ListNode last; public void addFirst(int data){ ListNode node = new ListNode(data); if(head == null){ head = node; last = node; }else{ node.next = head; head.prev = node; head = node; } } public void display(){ ListNode cur = head; while(cur != null){ System.out.println(cur.val + " "); cur = cur.next; } System.out.println(); } public void addLast(int data){ ListNode node = new ListNode(data); if(head == null){ head = node; last = node; }else{ last.next = node; node.prev = last; last = node; } } public boolean contains(int key){ ListNode cur = head; while(cur != null){ if(cur.val == key){ return true; } cur = cur.next; } return false; } public int size(){ int count = 0; ListNode cur = head; while(cur != null){ count++; cur = cur.next; } return count; } public void addIndex(int index,int data){ int size = size(); if(index < 0 || index > size){ System.out.println("下标位置不合法" + index); } if(index == 0){ addFirst(data); } if(index == size){ addLast(data); } ListNode cur = search(index); ListNode node = new ListNode(data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; } private ListNode search(int index){ ListNode cur = head; while(index != 0){ cur = cur.next; index--; } return cur; } public void remove(int key){ ListNode cur = head; while(cur != null){ if(cur.val == key){ if(cur == head){ head = head.next; if(head == null){ last = null; }else { head.prev = null; } }else{ if(cur == last){ last = last.prev; last.next = null; }else{ cur.prev.next = cur.next; cur.next.prev = cur.prev; } } } cur = cur.next; } } public void clear(){ ListNode cur = head; while(cur != null){ ListNode curN = cur.next; cur.prev = null; cur.next = null; cur = curN; } last = null; head = null; } }