【数据结构】顺序表和链表重点知识汇总（附有代码）

1. public class MyArrayList {
2. 
3. public int[] elem;
4. public int usedSize;//当前顺序表中元素的个数
5. private static final int DEFAULT_CAPACITY = 10;//给定一个默认的容量
6. 
7. public MyArrayList(){
8.         elem = new int[DEFAULT_CAPACITY];
9.     }
10. 
11. //打印顺序表
12. public void diaplay(){
13. for (int i = 0; i < usedSize; i++) {
14.             System.out.print(elem[i]+" ");
15.         }
16.         System.out.println();
17.     }
18. //判断顺序表有没有满
19. private boolean isFull(){
20. return usedSize == elem.length;
21.     }
22. 
23. //增加元素时检查下标是否合法
24. private void checkPos1(int pos) {
25. if(pos < 0 || pos > usedSize){
26. return;
27.         }
28.     }
29. 
30. //修改查找元素时检查下标是否合法
31. private void checkPos2(int pos){
32. if(pos<0 || pos >= usedSize){
33. return;
34.         }
35.     }
36. //增加元素（尾插）
37. public void add(int data){
38. if(isFull()){
39.             elem = Arrays.copyOf(elem,elem.length*2);
40.         }
41.         elem[usedSize] = data;
42.         usedSize++;
43.     }
44. 
45. //在pos位置上增加元素
46. public void add(int pos,int data){
47.         checkPos1(pos);
48. if(isFull()){
49.             elem = Arrays.copyOf(elem,elem.length*2);
50.         }
51. //注意是 i>=pos
52. for (int i = usedSize-1; i >= pos; i--) {
53.             elem[i+1] = elem[i];
54.         }
55.         elem[pos] = data;
56.         usedSize++;
57.     }
58. 
59. //判断是否包含某个元素
60. public boolean contains(int data){
61. //i最多会走到usedSize的前一个元素，所以usedSize不用-1
62. for (int i = 0; i < usedSize; i++) {
63. if(data == elem[i]){
64. return true;
65.             }
66.         }
67. return false;
68.     }
69. 
70. //找到某个元素的下标
71. public int indexOf(int data){
72. for (int i = 0; i < usedSize; i++) {
73. if(data == elem[i]){
74. return i;
75.             }
76.         }
77. return -1;
78.     }
79. 
80. //获取pos下标的元素
81. public int get(int pos){
82.         checkPos2(pos);
83. return elem[pos];
84.     }
85. 
86. //将pos位置的值改成value
87. public void set(int pos,int value){
88.         checkPos2(pos);
89.         elem[pos] = value;
90.     }
91. 
92. //删除第一次出现的关键字key
93. public void remove(int key){
94. int index = indexOf(key);
95. if(index == -1){
96.             System.out.println("找不到这个数字");
97.         }
98.         checkPos2(index);
99. //这里注意一下：一定要-1
100. for (int i = index; i < usedSize-1; i++) {
101.             elem[i] = elem[i+1];
102.         }
103.         usedSize--;
104.     }
105. 
106. //获取顺序表的长度
107. public int size(){
108. /*int count = 0;
109.         for (int i = 0; i < usedSize; i++) {
110.             count++;
111.         }
112.         return count;*/
113. return usedSize;
114.     }
115. 
116. //清空顺序表
117. public void clear(){
118. /*for (int i = 0; i < usedSize; i++) {
119.             elem[i]=null;
120.         }*/
121.         usedSize = 0;
122.     }
123. 
124. }

1. public class MySingleList {
2. 
3. static class ListNode{
4. public int val;
5. public ListNode next;
6. 
7. public ListNode(int val) {
8. this.val = val;
9.         }
10.     }
11. public ListNode head;
12. 
13. //头插法
14. public void addFirst(int data){
15. ListNode node = new ListNode(data);
16.         node.next = head;
17.         head = node;
18.     }
19. 
20. //尾插法
21. public void addLast(int data){
22. ListNode node = new ListNode(data);
23. if(head == null){
24.             head = node;
25.         }else{
26. ListNode cur = head;
27. while(cur.next != null){
28.                 cur = cur.next;
29.             }
30.             cur.next = node;
31.         }
32.     }
33. 
34. //打印链表
35. public void display(){
36. ListNode cur = head;
37. while(cur != null){
38.             System.out.print(cur.val+" ");
39.             cur = cur.next;
40.         }
41.         System.out.println();
42.     }
43. 
44. //从指定节点打印
45. public void display(ListNode newHead){
46. ListNode cur = newHead;
47. while(cur != null){
48.             System.out.print(cur.val+" ");
49.             cur = cur.next;
50.         }
51.         System.out.println();
52.     }
53. 
54. //查找元素key是否在单链表中
55. public boolean contains(int key){
56. ListNode cur = head;
57. while(cur != null){
58. if(cur.val == key){
59. return true;
60.             }
61.             cur = cur.next;
62.         }
63. return false;
64.     }
65. 
66. //得到链表的长度
67. public int size(){
68. ListNode cur = head;
69. int count = 0;
70. while(cur != null){
71.             count++;
72.             cur = cur.next;
73.         }
74. return count;
75.     }
76. 
77. //插入元素时检查下标合法性
78. private void checkIndex(int index) {
79. if(index < 0 || index > size()){
80. return;
81.         }
82.     }
83. 
84. //任意位置插入元素,首元素若为0下标
85. public void addIndex(int index,int data){
86.         checkIndex(index);
87. if(index == 0){
88.             addFirst(data);
89. return;
90.         } else if (index == size()) {
91.             addLast(data);
92. return;
93.         }else {
94. ListNode node = new ListNode(data);
95. ListNode cur = head;
96. while (index - 1 != 0) {
97.                 cur = cur.next;
98.                 index--;
99.             }
100.             node.next = cur.next;
101.             cur.next = node;
102.         }
103. 
104.     }
105. 
106. //删除第一次出现的元素key
107. public void remove(int key){
108. if(head.val == key){
109.             head = head.next;
110. return;
111.         }
112. ListNode cur = head;
113. //循环中时cur.next，如果是cur的话会空指针异常
114. while(cur.next != null){
115. //这里处理不了头节点
116. if(cur.next.val == key){
117.                 cur.next = cur.next.next;
118. return;
119.             }
120.             cur = cur.next;
121.         }
122.     }
123. 
124. //删除所有值为key的元素。只遍历了一遍！！
125. public void removeAll(int key){
126. if(head == null){
127. return;
128.         }
129. ListNode cur = head;
130. ListNode prev = head;
131. 
132. while(cur != null){
133. if(cur.val == key){
134.                 prev.next = cur.next;
135.                 cur = cur.next;
136.             }else{
137.                 prev = cur;
138.                 cur = cur.next;
139.             }
140.         }
141. if(head.val == key){
142.             head = head.next;
143.         }
144.     }
145. 
146. //清空链表
147. public void clear(){
148. ListNode cur = head;
149. while(cur != null){
150. ListNode curNext = cur.next;
151.             cur.next = null;
152.             cur = curNext;
153.         }
154.         head = null;
155.     }
156. 
157. }