数据结构之链表

一、学习心得

我们常用的数据结构就这几种数组、链表、树、map(映射)，而这些结构又紧密相连，互相表达；在我看来HashMap是基于数组的映射，TreeMap是基于树的映射,Java中的数组实际是JVM给你在内存(堆)中创建的连续空间，内存划分是连续的；链表的实质是一个个对象，但是对象会携带前或后(数学表示前，后，前后)元素的指针(引用，内存地址)，树和链表有些相似，树是从根节点出发的，每个节点都有自己的左右孩子，还有一个父亲节点。

1、HashMap，在数组的基础上加上了hash算法，每个元素都有一个hash值，按HashCode来存储元素,如果hashcode一样，可采用链地址法在该元素下面接一个个的其他元素；

再来浅谈为什么一个类覆盖了equals方法为什么还需要覆盖hashcode方法，因为hash值相等不一定这2个对象是一样的，但是用equals方法比较这个对象的属性都相等，那么这个对象就一定相等，相等一般的业务需要就是：对象相等那么其HashCode值也要相等，不然就造成程序内存过多的开销与bug出现。

2、TreeMap，在树结构的基础上加上hash算法

二、链表

2.1、单向链表

链表添加元素不同于数组，它可以从左边开始添加，也可以从右边开始添加；也就是常说的头插法和尾插法，废话不多说，直接上才艺。
链表对象

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
    }

    // 链表结点的构造函数
    // 使用arr为参数，创建一个链表，当前的ListNode为链表头节点
    public ListNode(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arr cannot be empty");
        }
        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    // 以当前节点为头节点的链表信息字符串
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            res.append(cur.val).append("->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

头插法

ListNode ans = null;
while(条件){
	ListNode curr = new ListNode(val);
	curr.next = ans; // 将当前元素指向上一个元素
	ans = curr; // 将结果赋值给answer
}
return ans;
1
2
3
4
5
6
7

尾插法

ListNode head = null, tail = null;
while(条件){
	if(head == null){
		head = tail = new ListNode(val);
	}else{
		tail.next = new ListNode(val);
		tail = tail.next;
	}
}
return head;
1
2
3
4
5
6
7
8
9
10

反转链表——迭代法

ListNode curr = head;
ListNode prev = null;
while(curr != null){
	ListNode next = curr.next; // 将当前节点与其后面的节点分离
	curr.next = prev; // 当前节点指向前一个结点
	prev = curr; // 暂存当前节点到前个节点，以待第二次循环
	curr = next; // 切换指针
}
return prev;
1
2
3
4
5
6
7
8
9

反转链表——递归法

    public ListNode reverseList(ListNode head) {

        if (head == null || head.next == null)
            return head;

        ListNode rev = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return rev;
    }
1
2
3
4
5
6
7
8
9
10

2.2、双向链表

有时间深入解读JavaLinkedList类

2.3、其他链表

功成归极乐，汝亦座莲台！