Trung tâm cá nhân
sách gpt4 ăn đã đi

Khái niệm cơ bản về cấu trúc dữ liệu java: danh sách liên kết đơn và đôi

In lại Tác giả: qq735679552 Thời gian cập nhật: 29-09-2022 22:32:09 36 4
mua khóa gpt4 giày nike

CFSDN nhấn mạnh vào giá trị tạo ra nguồn mở và chúng tôi cam kết xây dựng nền tảng chia sẻ tài nguyên để mọi nhân viên CNTT có thể tìm thấy thế giới tuyệt vời của bạn tại đây.

Bài viết trên blog CFSDN Kiến thức cơ bản về cấu trúc dữ liệu Java: danh sách liên kết đơn và kép được tác giả sưu tầm và biên soạn. Nếu các bạn quan tâm đến bài viết này thì nhớ like nhé.

danh sách liên kết một chiều

Ưu điểm lớn nhất của danh sách liên kết một chiều so với danh sách tuyến tính có cấu trúc tuần tự là nó không cần đảm bảo vị trí lưu trữ. Nó chỉ cần sử dụng con trỏ để trỏ đến phần tử tiếp theo.

Sơ đồ danh sách liên kết đơn

Khái niệm cơ bản về cấu trúc dữ liệu java: danh sách liên kết đơn và đôi

Hình ảnh khá thô nên tôi sẽ giải thích ngắn gọn cho bạn:

Mỗi hình trong số bốn hình chữ nhật ở trên là một nút. Trong hình chữ nhật, một cái chứa hai thứ, một là phần tử của nút hiện tại và cái còn lại là địa chỉ trỏ đến nút tiếp theo. Địa chỉ của nút tiếp theo này trỏ đến phần tử trong nút tiếp theo. Và vân vân.

Nút ở phía bên trái được gọi là nút đầu và tương tự, nút ở cuối được gọi là nút đuôi.

Do đó, tất cả các hoạt động của chúng tôi được thực hiện dựa trên các nút.

mã số

Các mã này có nhận xét rất chi tiết nên tôi sẽ không giải thích quá nhiều. Bạn chỉ cần sao chép mã vào ý tưởng cục bộ của mình và chạy một lần là bạn sẽ biết mọi thứ.

?
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
bưu kiện com.zxy.lianbiao;
/**
  * @Author Zxy
  * @Ngày 2021/2/3 21:25
  * @Version 1.0
  */
/**
  * Triển khai truy cập phần tử dựa trên danh sách liên kết một chiều
  *
  * @param
  */
công cộng lớp học Danh sách liên kết đơn lẻ của tôi thực hiện Danh sách của tôi {
     /**
      * Xác định các đối tượng nút trong danh sách liên kết một chiều
      */
     lớp học Nút {
         riêng tư Và mục; // lưu trữ các phần tử
         riêng tư Nút tiếp theo; // Lưu trữ đối tượng nút tiếp theo
         công cộng Node(E mục, Node tiếp theo) {
             cái này .item = mục;
             cái này .next = tiếp theo;
         }
     }
     riêng tư Đầu nút; // Lưu nút đầu vào danh sách liên kết
     riêng tư số nguyên kích cỡ; //Ghi lại số phần tử
     /**
      * Thêm phần tử vào danh sách liên kết
      *
      * Phần tử @param
      */
     @Ghi đè
     công cộng vô hiệu thêm(phần tử E) {
         //Tạo nút
         nút nút = mới Node<>(phần tử, vô giá trị );
         // Tìm nút đuôi
         Nút đuôi = getTail();
         // Móc nút
         nếu như (đuôi == vô giá trị ) { // Nếu không có nút đuôi nghĩa là nút đầu không tồn tại.
             // Nếu không có nút đầu thì giao nút đã tạo cho nút đầu
             cái này .head = nút;
         } khác {
             tail.next = nút;
         }
         //Ghi lại số phần tử
         cái này .size++;
     }
     /**
      * Tìm nút đuôi
      */
     riêng tư Nút getTail() {
         // Xác định xem nút đầu có tồn tại không
         nếu như ( cái này .đầu == vô giá trị ) {
             trở lại vô giá trị ;
         }
         // Tìm nút đuôi
         Nút nút = cái này .cái đầu;
         trong khi ( ĐÚNG VẬY ) {
             nếu như (node.next == vô giá trị ) {
                 phá vỡ ;
             }
             node = node.next; // Di chuyển con trỏ tới phần tiếp theo
         }
         trở lại nút;
     }
     /**
      * Lấy phần tử dựa trên vị trí của nó
      *
      * @param chỉ mục
      * @trở lại
      */
     @Ghi đè
     công cộng E lấy( số nguyên chỉ số) {
         // Kiểm tra tính hợp lệ của chỉ mục
         cái này .checkIndex(chỉ mục);
         // Lấy nút được chỉ định dựa trên vị trí
         nút nút = cái này .getNode(chỉ mục);
         //Trả về các phần tử trong nút này
         trở lại node. mục;
     }
     /**
      * Xác minh chỉ số
      */
     riêng tư vô hiệu kiểm traIndex( số nguyên chỉ số) {
         // 0<=chỉ số
         nếu như (!(chỉ số >= 0 && chỉ mục < cái này .kích cỡ)) {
             ném mới Ngoại lệ IndexOutOfBounds( "Mục lục: " + mục lục + "kích thước này: " + cái này .kích cỡ);
         }
     }
     /**
      * Nhận các nút dựa trên vị trí
      */
     riêng tư Nút lấy Nút( số nguyên chỉ số) {
         nút nút = cái này .cái đầu;
         vì ( số nguyên tôi = 0 ; i < chỉ số; i++) {
             node = node.next;
         }
         trở lại nút;
     }
     /**
      * Lấy số phần tử
      *
      * @trở lại
      */
     @Ghi đè
     công cộng số nguyên kích cỡ() {
         trở lại cái này .kích cỡ;
     }
     /**
      * Xóa các phần tử dựa trên vị trí của chúng
      *
      * @param chỉ mục
      * @trở lại
      */
     @Ghi đè
     công cộng E xóa( số nguyên chỉ số) {
         // Kiểm tra tính hợp lệ của chỉ mục
         cái này .checkIndex(chỉ mục);
         // Tìm đối tượng nút dựa trên vị trí
         Nút nút = getNode(index);
         // Lấy các phần tử trong đối tượng nút
         Mục E = node.item;
         //Xóa đối tượng nút khỏi danh sách liên kết một chiều
         // Xác định xem nút hiện đang bị xóa có phải là nút đầu không
         nếu như ( cái này .head == nút) {
             cái này .head = node.next;
         } khác {
             Nút nhiệt độ = cái này .cái đầu;
             vì ( số nguyên tôi = 0 ; tôi < chỉ mục - 1 ; tôi++) {
                 temp = temp.next; // Nhiệt độ tại thời điểm này là nút trước nút bị xóa.
             }
             temp.next = node.next; // Trỏ nút trước của nút hiện tại tới nút sau nút hiện tại
         }
         // Sau đó trỏ nút tiếp theo của nút hiện tại thành null
         node.next = vô giá trị ;
         // 记录元素个数
         cái này .size--;
         //Trả về phần tử này
         trở lại mục;
     }
     /**
      * Chèn ý tưởng nút: Nếu hiện tại có 3 nút là 1, 2 và 3 thì chèn 4 vào giữa 1 và 2. Cách trỏ ban đầu là 1->2, nay đổi thành 1->4 4->2. Lấy nó trước. Chỉ định nút ở vị trí, sau đó lấy nút ở vị trí trước đó và nút ở vị trí tiếp theo.
      */
     công cộng vô hiệu chèn( số nguyên chỉ số, phần tử E) {
         // Đầu tiên lấy đối tượng nút tại vị trí này theo vị trí cần chèn.
         Mục Node = getNode(index);
         // Tạo một nút mới dựa trên phần tử được chèn
         Nút eNode = mới Node<>(phần tử, vô giá trị );
         // Nếu là nút đầu thì không thể tìm thấy nút trước đó và giá trị này được gán trực tiếp cho đầu.
         nếu như (mục lục == 0 ){
             // index==0 có nghĩa là thay thế nút quay đầu
             cái này .head = eNode;
             eNode.next = mục;
             cái này .size++;
         } khác {
             // Tìm đối tượng nút trước và đối tượng nút tiếp theo dựa trên đối tượng nút hiện tại
             Nút trước = cái này .cái đầu; // Tìm dựa trên nút đầu
             vì ( số nguyên tôi = 0 ; tôi < chỉ mục - 1 ; tôi++) {
                 trước = trước.tiếp theo; // Nút trước tại thời điểm này là nút trước nút hiện tại.
             }
             before.next = eNode;
             eNode.next = mục;
             cái này .size++;
         }
     }
     công cộng tĩnh vô hiệu main(String[] args) {
         Danh sách MySinglyLinkedList = mới Danh sách liên kết của tôi<>();
         Hệ thống.out.println( "Bắt đầu thêm nút--------------" );
         list.add((Chuỗi) "Một" );
         list.add((Chuỗi) "b" );
         list.add((Chuỗi) "c" );
         list.add((Chuỗi) "đ" );
         Hệ thống.out.println( "Thêm nút đã hoàn tất--------------------------\n" );
         Hệ thống.out.println( "Chèn phần tử được chỉ định" );
         danh sách.chèn( 0 , "f" );
         vì ( số nguyên tôi = 0 ; i < kích thước danh sách; i++) {
             System.out.println(danh sách.get(i));
         }
     }
}

danh sách liên kết đôi

Hôm qua sau khi viết xong về danh sách liên kết một chiều và cấu trúc ngăn xếp, tôi đã đọc phần về danh sách liên kết đôi trong sách của Cheng Jie. Mặc dù nó được viết bằng ngôn ngữ C nhưng tôi vẫn dịch nó bằng Java.

Ý tưởng là như sau:

Trước hết, sự khác biệt lớn nhất giữa danh sách liên kết đôi và danh sách liên kết đơn là danh sách liên kết đôi có thêm một con trỏ tới nút trước đó so với danh sách liên kết đơn. Số lượng code thực ra không nhiều hơn nhiều so với danh sách liên kết đơn, nhưng cần phải khắc phục sự thay đổi trong tư duy.

Thứ hai, khi chèn phần tử, chúng ta có thể chèn vào đầu danh sách liên kết hoặc vào cuối danh sách liên kết (vì có 2 con trỏ).

mã hóa

Mã thực sự tương tự như một danh sách liên kết đơn. Nếu quan tâm, bạn có thể đọc bài viết tôi đã viết về danh sách liên kết đơn trước đây. Mặc dù văn bản rất tệ, nhưng mã là chính hãng.

?
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
bưu kiện com.zxy.lianbiao;
/**
  * @Author Zxy
  * @Ngày 2021/2/4 20:11
  * @Version 1.0
  */
/**
  * Vùng chứa thực hiện truy cập phần tử dựa trên danh sách liên kết đôi
  *
  * @param
  */
công cộng lớp học Danh sách liên kết của tôi thực hiện Danh sách của tôi {
 
     /**
      * Xác định đối tượng nút danh sách liên kết đôi
      */
     lớp học Nút {
         Và mục; //Ghi lại các phần tử
         Nút trước; //Ghi lại đối tượng nút trước đó
         Nút tiếp theo; //Ghi lại đối tượng nút tiếp theo
         công cộng Node(Node trước, mục E, Node tiếp theo) {
             cái này .item = mục;
             cái này .prev = trước;
             cái này .next = tiếp theo;
         }
     }
     riêng tư Đầu nút; //Ghi lại nút đầu
     riêng tư Đuôi nút; //Ghi lại nút đuôi
     riêng tư số nguyên kích cỡ; // 记录元素个数
     /**
      * Phương pháp thêm phần tử vào danh sách liên kết đôi
      *
      * Phần tử @param
      */
     @Ghi đè
     công cộng vô hiệu thêm(phần tử E) {
         linkLast(phần tử);
     }
     /**
      * Thêm đối tượng nút vào cuối danh sách liên kết đôi
      */
     riêng tư vô hiệu linkLast(phần tử E) {
         Nút t = cái này .đuôi; // Lấy nút đuôi
         nút nút = mới Node<>(t, phần tử, vô giá trị ); //Tạo đối tượng nút
         cái này .tail = nút; // Xác định nút mới là nút đuôi vì nút đuôi ban đầu được thay thế bằng nút mới này
         nếu như (t == vô giá trị ) {
             // Biểu thị rằng không có nút nào, đây phải là nút đầu
             cái này .head = nút;
         } khác {
             t.next = nút;
         }
         cái này .size++;
     }
     /**
      * Lấy phần tử dựa trên vị trí đã chỉ định
      *
      * @param chỉ mục
      * @trở lại
      */
     @Ghi đè
     công cộng E lấy( số nguyên chỉ số) {
         cái này .checkIndex(chỉ mục);
         // Tìm đối tượng nút dựa trên vị trí
         nút nút = cái này .getNode(chỉ mục);
         trở lại node. mục;
     }
     /**
      * Xác minh tính hợp lệ của chỉ mục
      */
     riêng tư vô hiệu kiểm traIndex( số nguyên chỉ số) {
         nếu như (!(chỉ số >= 0 && chỉ mục < cái này .kích cỡ)) {
             ném mới Ngoại lệ IndexOutOfBounds();
         }
     }
     /**
      * Lấy đối tượng nút được chỉ định dựa trên vị trí
      */
     riêng tư Nút getNode( số nguyên chỉ số) {
         // Xác định nút nào có vị trí hiện tại gần hơn, đầu hay đuôi, sử dụng phương pháp phân đôi
         nếu như (chỉ số < ( cái này .kích thước >> 1 )) {
             Nút nút = cái này .cái đầu;
             vì ( số nguyên tôi = 0 ; i < chỉ số; i++) {
                 node = node.next;
             }
             trở lại nút;
         } khác {
             Nút nút = cái này .đuôi;
             vì ( số nguyên tôi = cái này .kích cỡ - 1 ; i > chỉ số; i--) {
                 node = node.prev;
             }
             trở lại nút;
         }
     }
     /**
      * Trả về số phần tử
      *
      * @trở lại
      */
     @Ghi đè
     công cộng số nguyên kích cỡ() {
         trở lại cái này .kích cỡ;
     }
     /**
      * Xóa phần tử
      *
      * @param chỉ mục
      * @trở lại
      */
     @Ghi đè
     công cộng E xóa( số nguyên chỉ số) {
         // Kiểm tra tính hợp lệ của chỉ mục
         cái này .checkIndex(chỉ mục);
         Nút nút = cái này .getNode(chỉ mục); // Lấy đối tượng nút dựa trên vị trí
         // Lấy các phần tử của đối tượng nút
         Mục E = (E) node.item;
         // Xác định xem nút hiện tại có phải là nút đầu không
         nếu như (node. trước == vô giá trị ) {
             cái này .head = node.next;
         } khác {
             node.prev.next = node.next;
         }
         // Xác định xem nút hiện tại có phải là nút đuôi không
         nếu như (node.next == vô giá trị ) {
             // node. trước. tiếp theo = null;
             cái này .tail = node.prev;
         } khác {
             node.next.prev = node.prev;
         }
         // Nút hiện tại ngắt kết nối với các nút kế tiếp của nó
         node.next = vô giá trị ;
         // Nút hiện tại ngắt kết nối với nút tiền nhiệm trực tiếp
         node.prev = vô giá trị ;
         node.item = vô giá trị ;
         cái này .size--;
         trở lại mục;
     }
     /**
      * Thêm một phần tử vào đầu danh sách liên kết đôi
      */
     công cộng vô hiệu addFirst(phần tử E) {
         cái này .linkFirst(phần tử);
     }
     /**
      * Thêm một phần tử vào đầu danh sách liên kết
      *
      * Phần tử @param
      */
     công cộng vô hiệu linkFirst(phần tử E) {
         // Lấy đối tượng nút đầu
         Đầu nút = cái này .cái đầu;
         Nút eNode = mới Nút<>( vô giá trị , phần tử, đầu);
         // Xác định nút mới là nút đầu
         cái này .head = eNode;
         nếu như (đầu == vô giá trị ) {
             // Nếu trống nghĩa là không có nút nào trong danh sách liên kết, tức là nút đầu cũng là nút đuôi.
             cái này .tail = eNode;
         } khác {
             head.prev = eNode;
         }
         cái này .size++;
     }
     /**
      * Thêm phần tử vào cuối danh sách liên kết
      *
      * Phần tử @param
      */
     công cộng vô hiệu addLast(phần tử E) {
         cái này .linkLast(phần tử);
     }
     công cộng tĩnh vô hiệu main(String[] args) {
         Danh sách MyDoublyLinkedList = mới Danh sách liên kết của tôi<>();
         danh sách.thêm( "Một" );
         danh sách.thêm( "b" );
         danh sách.thêm( "c" );
         danh sách.thêm( "đ" );
         danh sách.thêm( "e" );
         System.out.println(danh sách.xóa( 2 ));
         System.out.println(kích thước danh sách);
         vì ( số nguyên tôi = 0 ; i < danh sách.kích thước(); i++) {
             System.out.println(danh sách.get(i));
         }
     }
}

Tóm tắt

Bài viết này kết thúc tại đây, tôi hy vọng nó có thể hữu ích cho bạn và tôi hy vọng bạn có thể chú ý hơn đến nội dung của tôi! .

Liên kết gốc: https://blog.csdn.net/weixin_43581288/article/details/113660067.

Cuối cùng, bài viết này về những kiến ​​thức cơ bản về cấu trúc dữ liệu Java: danh sách liên kết đơn và đôi sẽ kết thúc ở đây. Nếu bạn muốn biết thêm về những kiến ​​thức cơ bản về cấu trúc dữ liệu Java: danh sách liên kết đơn và kép, vui lòng tìm kiếm các bài viết CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng tất cả các bạn sẽ ủng hộ blog của tôi trong tương lai! .

36 4 0
Đề xuất bài viết: Người dùng mới của Call of Duty sẽ nhận được tiền thưởng từ 1 RMB đến 188 RMB.
Đề xuất bài viết: Quét Xiaohongshu để rút một phong bì tiền mặt màu đỏ ngẫu nhiên cho bài kiểm tra cá nhân 0,28 nhân dân tệ
Đề xuất bài viết: Giải thích chi tiết về mã hóa động của các bộ byte ngôn ngữ dễ dàng
Đề xuất bài viết: 完成简单答题抽随机现金红包 亲测秒到0.68元
qq735679552
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress