数据结构与算法-1

线性结构

一、数组（Array）

数组的砖块整齐排列，逐个紧贴。

链表的砖块分散各处，连接的藤蔓自由地穿梭于砖缝之间。

数组是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。

我们将元素在数组中的位置称为该元素的索引（index）。

image-20250320150520541

常用操作

==int[] num = new int[]{ 1, 3, 2, 5, 4 };==
==set(int index, int value)== ：给指定位置元素赋值，O(1)
==get(int index)== ：获取指定位置元素，O(1)
==length()== ：获取数组长度，O(1)

1.1 初始化数组

我们可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。

1
2
3
int[] arr = new int[5];    // { 0, 0, 0, 0, 0 }
int[] nums = { 1, 3, 2, 5, 4 };
int[] num = new int[]{ 1, 3, 2, 5, 4 };

1.2 访问元素

数组元素被存储在连续的内存空间中，计算数组元素的内存地址非常容易。给定数组内存地址（首元素内存地址）和某个元素的索引。

image-20250320150641936

1.3 插入元素

数组元素在内存中是“紧挨着的”，它们之间没有空间再存放任何数据。如果想在数组中间插入一个元素，则需要将==该元素之后的所有元素都向后移动一位==，==之后再把元素赋值给该索引==。

image-20250320150806648

值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素“丢失”。我们将这个问题的解决方案留在“列表”章节中讨论。

1
2
3
4
5
6
void insert(int[] nums, int num, int index) {
    for (int i = nums.length - 1; i > index; i--) {
        nums[i] = nums[i - 1];  // 把索引 index 以及之后的所有元素向后移动一位
    }
    nums[index] = num;
}

1.4 删除元素

若想删除索引 i 处的元素，则需要把索引 i 之后的元素都向前移动一位。

image-20250320150956311 
1
2
3
4
5
void remove(int[] nums, int index) {
    for (int i = index; i < nums.length - 1; i++) {
        nums[i] = nums[i + 1];   // 把索引 index 之后的所有元素向前移动一位
    }
}

总的来看，数组的插入与删除操作有以下缺点:

  • 时间复杂度高：数组的插入和删除的平均时间复杂度均为 $O(n) $，其中$ n$ 为数组长度。
  • 丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。
  • 内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做会造成部分内存空间浪费。

1.5 遍历数组

在大多数编程语言中，我们既可以通过索引遍历数组，也可以直接遍历获取数组中的每个元素：

1
2
3
4
5
6
7
8
9
10
11
void traverse(int[] nums) {
    int count = 0;
    // 通过索引遍历数组
    for (int i = 0; i < nums.length; i++) {
        count += nums[i];
    }
    // 直接遍历数组元素
    for (int num : nums) {
        count += num;
    }
}

1.6 查找元素

在数组中查找指定元素需要遍历数组，每轮判断元素值是否匹配，若匹配则输出对应索引。

因为数组是线性数据结构，所以上述查找操作被称为“线性查找”。

1
2
3
4
5
6
7
int find(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target)
            return i;
    }
    return -1;
}

1.7 扩容数组

程序难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量。因此在大多数编程语言中，数组的长度是不可变的。

如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次复制到新数组。这是一个$ O(n) $的操作，在数组很大的情况下非常耗时。代码如下所示：

1
2
3
4
5
6
7
int[] extend(int[] nums, int enlarge) {
    int[] res = new int[nums.length + enlarge];
    for (int i = 0; i < nums.length; i++) {
        res[i] = nums[i];
    }
    return res;
}

数组访问$ O(1) $快，查询删除$ O(n) $慢。

二、动态数组（ArrayList）

我们将把“列表”和“动态数组”视为等同的概念。

  • 泛型

    使用泛型技术可以让动态数组更通用，可以存放任何数据类型。

    类型名< E >，E只能放对象类型。后面用到E的地方均可变。

1
2
3
4
5
private int[] elements; 	 
private   E[] elements; 

int[] newElements =  	  new int[newCapacity];
  E[] newElements = (E[]) new Object[newCapacity]; // 强制类型转换 ######

2.1 常用操作

==List emptyList = new ArrayList<>();==
==add(int element)== ：在数组末尾添加元素，均摊 O(1)
==add(int index, int element)== ：在指定索引处添加元素，平均 O(n)
==get(int index)== ：获取指定索引处的元素，O(1)
==set(int index, int element)== ：更新指定索引处的元素，O(1)
==remove(int index)== ：移除指定索引处的元素，平均 O(n)
==removeElement(Integer element)== ：移除指定元素，平均 O(n)
==size()== ：获取动态数组长度，O(1)
==isEmpty()== ：判断是否为空，O(1)

2.2 动态数组自实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
public class ArrayList<E> {   // ArrayList<E>表示泛型类，E 表示数组中存储元素的类型
	
	private int size; 	   // 记录当前数组中实际存储的元素数量
	private E[] elements;  // 用于存储元素的数组   private int[] elements;
	
	private static final int DEFAULT_CAPACITY = 10;	   //默认容量10
	private static final int ELEMENT_NOT_FOUND = -1;  //没找到元素返回-1
	
//* 有参构造。防止capaticy传入的是负数或0。ArrayList list = new ArrayList(capaticy);
	public ArrayList(int capaticy) {
		capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
	 
        // elements = new int[capaticy];
		elements = (E[]) new Object[capaticy]; // ## 强制转换
	}
	
//* 无参构造。调用有参构造方法并传入默认容量。 ArrayList list = new ArrayList();
	public ArrayList() {
		this(DEFAULT_CAPACITY);  
	}
	
//*  clear。清除所有元素
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;  
	}

//  size。元素的数量  
	public int size() {
		return size;
	}

//  isEmpty。是否为空  
	public boolean isEmpty() {
		 return size == 0;
	}
	
//  contains。是否包含某个元素。 调用indexOf方法查找元素的索引，如果索引不为-1，则表示包含该元素。
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}
    
//  indexOf。indexOf方法查找元素的索引。 
	public int indexOf(E element) {
		if (element == null) {  	// null.equals(elements[i])，null equals报错######
			for (int i = 0; i < size; i++) {
				if (elements[i] == null)  return i; 
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (element.equals(elements[i]))  return i; 
			}
		}
		return ELEMENT_NOT_FOUND;
	}
    
//  add。添加元素到尾部  
	public void add(E element) {
		add(size, element);
	}
    
//  add。在index位置插入一个元素，索引大的先挪
	public void add(int index, E element) {
		rangeCheckForAdd(index); // 索引约束
		
		ensureCapacity(size + 1); // 保证有size + 1的容量
		
		for (int i = size; i > index; i--) {  // 将插入位置(index)之后的元素依次向后移动一位。
			elements[i] = elements[i - 1]; 
		}
		elements[index] = element;
		size++;
	}

//  get。获取index位置的元素  对index索引做约束 
	public E get(int index) {
		rangeCheck(index); 
		return elements[index];
	}

// set。设置index位置的元素  原来的先取出来，新的覆盖掉旧的，返回原来元素
	public E set(int index, E element) {
		rangeCheck(index);
		
		E old = elements[index]; 
		elements[index] = element; 
		return old; 
	}
 
//  remove。删除index位置的元素，返回被删除元素，索引小的先挪
	public E remove(int index) {
		rangeCheck(index);
		
		E old = elements[index];
		for (int i = index + 1; i < size; i++) {
			elements[i - 1] = elements[i];
		}
		elements[--size] = null;  // --size 先减后用(用的是减完后的值)
		return old;
	}
		
//  ensureCapacity。动态扩容。保证要有capacity的容量
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length; 		// 旧容量
		if (oldCapacity >= capacity)    return; // 不需要扩容，返回
		
		// 新容量为旧容量的1.5倍 oldCapacity*1.5费时间，右移>>÷2，<<*2
		int newCapacity = oldCapacity + (oldCapacity >> 1);
        
		// int[] newElements =  new int[newCapacity];
		E[] newElements = (E[]) new Object[newCapacity]; // 强制转换
        
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i]; // 拷贝数组
		}
		elements = newElements;
		System.out.println(oldCapacity + "扩容为" + newCapacity);
	}
	
// rangeCheck。检查索引范围是否越界。
	private void rangeCheck(int index) {
		if (index < 0 || index >= size) {  // ### >=
			throw new IndexOutOfBoundsException("Index:" + index + "，Size:" + size);
		}
	}
	
// rangeCheckForAdd。检查添加索引范围是否越界。
	//  ***get set remove数组中已存在元素，故索引0到size-1，index = size不行。// ### >=
	//  ***add 插入元素，允许index = size。// ### >
	private void rangeCheckForAdd(int index) {
		if (index < 0 || index > size) {   // ### >
			throw new IndexOutOfBoundsException("Index:" + index + "，Size:" + size);
		}
	}
	
// 打印数组。重写toString方法，否则打印出来的是地址，以字符串形式输出
	@Override
	public String toString() {
		// size=3, [99, 88, 77]，字符串拼接最好使用StringBuilder
		StringBuilder string = new StringBuilder();
		string.append("size=").append(size).append(", [");
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				string.append(", ");
			}
			string.append(elements[i]);	
            //  string.append(elements[i]);	
			//  if (i != size - 1) {
			//  	string.append(", ");
  			//  }上面的方法不用做减法
		}
		string.append("]");
		return string.toString();
	}
}

三、链表（Linkedlist）

链表是一种线性数据结构，其中的每个元素都是==一个节点对象==，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

image-20250320151200631

链表的组成单位是==节点（node）对象==。每个节点都包含两项数据：==节点的“值”==和==指向下一节点的“引用”==。

链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”。

在 C、C++、Go 和 Rust 等支持指针的语言中，上述“引用”应被替换为“指针”。

链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。

1
2
3
4
5
6
/* 链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向下一节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

常用操作

==List list = new LinkedList<>();==
==add()== ：在指定位置或末尾添加元素 ，平均 O(n)，末尾添加 O(1)
==get()== ：获取指定位置的元素，O(n)
==remove()== ：移除指定位置或指定元素，平均 O(n) ，移除末尾或头节点 O(1)
==size()== ：获取链表长度，O(n)
==contains()== ：判断是否包含某个元素，O(n)

3.1 初始化链表

建立链表分为两步，第一步是初始化各个节点对象，第二步是构建节点之间的引用关系。

初始化完成后，我们就可以从链表的头节点出发，通过引用指向 next 依次访问所有节点。

1
2
3
4
5
6
7
8
9
10
11
12
/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// 构建节点之间的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

==数组整体是一个变量==，比如数组 nums 包含元素 nums[0] 和 nums[1] 等。

而链表是由多个独立的节点对象组成的。通常==将头节点当作链表的代称==，如以上代码的链表可记作链表 n0 。

3.2 插入节点

在链表中插入节点非常容易。

假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需改变两个节点引用（指针）即可，时间复杂度为$O(1)$。

在数组中插入元素的时间复杂度为 $O(n)$ ，在大数据量下的效率较低。

image-20250320151247456 
1
2
3
4
5
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next; // ***
    P.next = n1;
    n0.next = P;
}

3.3 删除节点

在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

image-20250320151503999 
1
2
3
4
5
6
7
8
9
/* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;
}

3.4 访问节点

在链表中访问节点的效率较低。

在 O(1) 时间下访问数组中的任意元素。

链表则不然，程序需要从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第 i 个节点需要循环 i−1 轮，时间复杂度为 $O(n)$ 。

1
2
3
4
5
6
7
8
9
/* 访问链表中索引为 index 的节点 */
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

3.5 查找节点

遍历链表，查找其中值为 target 的节点，输出该节点在链表中的索引。也属于线性查找。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
/* 在链表中查找值为 target 的首个节点 */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

3.6 常见的链表类型

  • 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
  • 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
  • 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。
1
2
3
4
5
6
7
/* 双向链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向后继节点的引用
    ListNode prev;  // 指向前驱节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

image-20250310171547340

3.7 单向链表的自实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
public class SinglyLinkedList<E>{
    private int size; 		// 元素的数量。声明了一个名为size的私有成员变量。
	private Node<E> first;	// 存储第一个节点的引用，用来找到整个链表。
    						// Node<E>是泛型类，用于表示链表中的节点，E表示链表存储的元素的类型。
    
    static final int ELEMENT_NOT_FOUND = -1;

	private static class Node<E>{	// Node类被声明为private static，它只属于LinkedList类
        E element;			// 存储在节点中的数据				
        Node<E> next;		// 指向下一个节点的引用
        public Node(E element, Node<E> next){
            this.element = element;
            this.next = next;
        }
    }

	public void clear(){
        size = 0;
        first = null;	// 后面元素没有被指向，被java虚拟机清除
    }

    // get。先取出节点，返回节点中的元素
	public E get(int index){
        return node(index).element; // node方法根据索引得到节点。node方法里已经检查了索引。
    }

    // 获取index位置对应的#节点#
	private Node<E> node(int index){
        rangeCheck(index);
        
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }
    
    // set。更改某索引位置的元素
	public E set(int index, E element){
        Node<E> node = node(index);	// node方法
        E old = node.element;
        node.element = element;
        return old;
    }

    // add。要在Index添加元素
    public void add(int index, E element){
        rangeCheckForAdd(index); // 检查索引，index是否在合法范围，否则抛出IndexOutOfBoundsException异常

        if(index == 0){			//在链表的开头插入元素。//否则 0-1 = -1
            first = new Node<>(element, first); //创建了一个新节点，并将这个节点设为first。
        } else {
            Node<E> prev = node(index - 1); // 找到指定索引的前一个节点
            prev.next = new Node<>(element, prev.next); //新节点插入到prev节点的后面;新节点的next引用指向原来prev的next节点。
        }
        size++;	// 链表的大小size增加1
    }

    // 根据索引删除元素
	public E remove(int index){
        rangeCheck(index); 			// 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;  
    }

    //  indexOf。查看元素的索引
	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;
    }
    
    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();
	}
   
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
	}

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    
}
  • 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
  • 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
  • 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

3.8 双向链表的自实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
public class LinkedList<E> {
	private Node<E> first;
	private Node<E> last;
	
	// 内部类：只在链表内部使用
	private static class Node<E> {
		E element; 		// 节点中的元素
		Node<E> prev; 	// 指向上一个Node
		Node<E> next; 	// 指向下一个Node
		
		public Node(Node<E> prev, E element, Node<E> next) {
			this.prev = prev;
			this.element = element;
			this.next = next;
		}
		
		public String toString() {
			StringBuilder sb = new StringBuilder();
			
			if (prev != null) {
				sb.append(prev.element);
			} else {
				sb.append("null");
			}
			
			sb.append("_").append(element).append("_");

			if (next != null) {
				sb.append(next.element);
			} else {
				sb.append("null");
			}
			
			return sb.toString();
		}
	}

    // clear。
	public void clear() {
		size = 0;
		first = null;
		last = null;
	}

	//	get(int index)。先取出节点，返回节点中的元素
	public E get(int index) {
		return node(index).element; // node方法里已经检查了索引
	}
    
    // 获取index位置对应的节点对象。
	private Node<E> node(int index) {
		rangeCheck(index);
		
		if (index < (size >> 1)) {
			Node<E> node = first;
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
			return node;
		} else {
			Node<E> node = last;
			for (int i = size - 1; i > index; i--) {
				node = node.prev;
			}
			return node;
		}
	}

	// set(int index, E element)。
	public E set(int index, E element) {
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

	// add(int index, E element)。要在Indext添加元素
	public void add(int index, E element) {
		rangeCheckForAdd(index);

		// size == 0  index == 0,0-1有问题
		if (index == size) { 		// 往最后面添加元素
			Node<E> oldLast = last;
			last = new Node<>(oldLast, element, null);
			if (oldLast == null) { // 这是链表添加的第一个元素
				first = last;
			} else {
				oldLast.next = last;
			}
		} else {
			Node<E> next = node(index); // 要往2添加元素，2即新添加结点的下一个
			Node<E> prev = next.prev;  	// 新添加结点的上一个
			Node<E> node = new Node<>(prev, element, next); // 新添加结点
			next.prev = node;
			
			if (prev == null) { 		// index == 0
				first = node;
			} else {
				prev.next = node;
			}
		}
		
		size++;
	}

	public E remove(int index) {
		rangeCheck(index);

		Node<E> node = node(index);
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		
		if (prev == null) { // index == 0
			first = next;
		} else {
			prev.next = next;
		}
		
		if (next == null) { // index == size - 1
			last = prev;
		} else {
			next.prev = prev;
		}
		
		size--;
		return node.element;
	}

	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;
	}
	
	@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(", ");
			}
			// node不是字符串，默认调用node的toString，toString返回什么拼接什么
			string.append(node);
			
			node = node.next;
		}
		string.append("]");
		return string.toString();
	}
}

9.循环链表的自实现

四、栈（Stack）

栈如同叠猫猫，而队列就像猫猫排队。

栈（stack）是一种遵循先入后出逻辑的线性数据结构。

我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。

将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。

image-20250320151713326

4.1 栈的常用操作

==Stack stack = new Stack<>();==

==push(int element)==：元素入栈（添加至栈顶），$ O(1)$

==pop()==：栈顶元素出栈，$ O(1)$

==peek()==：访问栈顶元素，$ O(1) $。

==size()==：获取长度

==isEmpty()==：是否为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 初始化栈 */
Stack<Integer> stack = new Stack<>();

/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);

/* 访问栈顶元素 */
int peek = stack.peek();

/* 元素出栈 */
int pop = stack.pop();

/* 获取栈的长度 */
int size = stack.size();

/* 判断是否为空 */
boolean isEmpty = stack.isEmpty();

4.2 基于链表实现栈

使用链表实现栈时，我们可以将==链表的头节点视为栈顶==，==尾节点视为栈底==。

对于入栈操作，只需将元素插入链表头部，这种节点插入方法被称为“头插法”。

对于出栈操作，只需将头节点从链表中删除即可。

image-20250320151926238

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/* 基于链表实现的栈 */
class LinkedListStack {
    private ListNode stackPeek; // 将头节点作为栈顶
    private int stkSize = 0; // 栈的长度

    public LinkedListStack() {
        stackPeek = null;
    }

    /* 获取栈的长度 */
    public int size() {
        return stkSize;
    }

    /* 判断栈是否为空 */
    public boolean isEmpty() {
        return size() == 0;
    }

    /* 入栈 */
    public void push(int num) {
        ListNode node = new ListNode(num);
        node.next = stackPeek;
        stackPeek = node;
        stkSize++;
    }

    /* 出栈 */
    public int pop() {
        int num = peek();
        stackPeek = stackPeek.next;
        stkSize--;
        return num;
    }

    /* 访问栈顶元素 */
    public int peek() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return stackPeek.val;
    }

    /* 将 List 转化为 Array 并返回 */
    public int[] toArray() {
        ListNode node = stackPeek;
        int[] res = new int[size()];
        for (int i = res.length - 1; i >= 0; i--) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }
}

浏览器中的后退与前进、软件中的撤销与反撤销。

4.3 基于数组实现栈

使用数组实现栈时，我们可以将数组的尾部作为栈顶。入栈与出栈操作分别对应在数组尾部添加元素与删除元素，时间复杂度都为$ O(1) $。

image-20250320152027308

由于入栈的元素可能会源源不断地增加，因此我们可以使用动态数组，这样就无须自行处理数组扩容问题。

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
35
36
37
38
39
40
41
42
43
/* 基于数组实现的栈 */
class ArrayListStack {
    private ArrayList<Integer> stack;

    public ArrayListStack() {
        // 初始化列表（动态数组）
        stack = new ArrayList<>();
    }

    /* 获取栈的长度 */
    public int size() {
        return stack.size();
    }

    /* 判断栈是否为空 */
    public boolean isEmpty() {
        return size() == 0;
    }

    /* 入栈 */
    public void push(int num) {
        stack.add(num);
    }

    /* 出栈 */
    public int pop() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return stack.remove(size() - 1);
    }

    /* 访问栈顶元素 */
    public int peek() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return stack.get(size() - 1);
    }

    /* 将 List 转化为 Array 并返回 */
    public Object[] toArray() {
        return stack.toArray();
    }
}

数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到。

五、队列（Queue）

队列（queue）是一种遵循先入先出规则的线性数据结构。

队列模拟了排队现象。新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

队列头部称为“队首”，尾部称为“队尾”，把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

image-20250320152608537

5.1 队列的常用操作

==Queue queue = new LinkedList<>();==

==offer(int element)==：元素入队，即将元素添加至队尾，$ O(1)$

==poll()==：队首元素出队，$ O(1)$

==peek()==：访问队首元素，$ O(1) $

==size()==：获取长度

==isEmpty()==：是否为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 初始化队列 */
Queue<Integer> queue = new LinkedList<>();  // ***

/* 元素入队 */
queue.offer(1);
queue.offer(3);
queue.offer(2);
queue.offer(5);
queue.offer(4);

/* 访问队首元素 */
int peek = queue.peek();

/* 元素出队 */
int pop = queue.poll();

/* 获取队列的长度 */
int size = queue.size();

/* 判断队列是否为空 */
boolean isEmpty = queue.isEmpty();

5.2 基于链表实现队列

我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点。

image-20250320152926710

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/* 基于链表实现的队列 */
class LinkedListQueue {
    private ListNode front, rear; // 头节点 front ，尾节点 rear
    private int queSize = 0;

    public LinkedListQueue() {
        front = null;
        rear = null;
    }

    /* 获取队列的长度 */
    public int size() {
        return queSize;
    }

    /* 判断队列是否为空 */
    public boolean isEmpty() {
        return size() == 0;
    }

    /* 入队 */
    public void push(int num) {
        // 在尾节点后添加 num
        ListNode node = new ListNode(num);
        // 如果队列为空，则令头、尾节点都指向该节点
        if (front == null) {
            front = node;
            rear = node;
        // 如果队列不为空，则将该节点添加到尾节点后
        } else {
            rear.next = node;
            rear = node;
        }
        queSize++;
    }

    /* 出队 */
    public int pop() {
        int num = peek();
        // 删除头节点
        front = front.next;
        queSize--;
        return num;
    }

    /* 访问队首元素 */
    public int peek() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return front.val;
    }

    /* 将链表转化为 Array 并返回 */
    public int[] toArray() {
        ListNode node = front;
        int[] res = new int[size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }
}

5.3 双向队列（Deque）

在队列中，我们仅能删除头部元素或在尾部添加元素。

双向队列提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

image-20250320153234571
方法名 功能 时间复杂度
==offerFirst()== 将元素添加至队首 O(1)
==offerLast()== 将元素添加至队尾 O(1)
==pollFirst()== 删除队首元素 O(1)
==pollLast()== 删除队尾元素 O(1)
==peekFirst()== 访问队首元素 O(1)
==peekLast()== 访问队尾元素 O(1) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 初始化双向队列 */
Deque<Integer> deque = new LinkedList<>();

/* 元素入队 */
deque.offerLast(2);   // 添加至队尾
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3);  // 添加至队首
deque.offerFirst(1);

/* 访问元素 */
int peekFirst = deque.peekFirst();  // 队首元素
int peekLast = deque.peekLast();    // 队尾元素

/* 元素出队 */
int popFirst = deque.pollFirst();  // 队首元素出队
int popLast = deque.pollLast();    // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.size();

/* 判断双向队列是否为空 */
boolean isEmpty = deque.isEmpty();
  • 双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。
  • 我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作push 到栈中，然后通过pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存50 步）。当栈的长度超过50 时，软件需要在栈底（队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。
  • 注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。
数据结构与算法分类
#线性结构---数组-链表-栈-队列
数据结构与算法-1
https://blog.xirui.work/posts/308d09c9.html
作者
xirui
发布于
2024年8月9日
许可协议