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 blog CFSDN này sử dụng võ thuật để hiểu mã nguồn Java LinkedList được tác giả sưu tầm và biên soạn. Nếu bạn quan tâm đến bài viết này thì nhớ like nhé.

1. Phân tích LinkedList

Xin chào mọi người, tôi là LinkedList và tôi là đồng môn của ArrayList, nhưng kỹ năng nội bộ của chúng tôi hoàn toàn khác nhau. Đồng nghiệp cao cấp của tôi đang thực hành mảng động và tôi đang thực hành danh sách liên kết.

Để tôi hỏi bạn một câu, bạn có biết tại sao tôi muốn rèn luyện kỹ năng nội bộ về danh sách liên kết không?

Ví dụ: bạn muốn quản lý một đống hóa đơn trong tay, có thể có một hoặc có thể có 100 triệu.

Phải làm gì?

Đăng ký mảng lớn 10G và chờ đợi? Nếu chỉ có 100 tờ tiền thì sao?

Áp dụng cho một mảng có kích thước mặc định và mở rộng nó khi lượng dữ liệu tăng lên? Bạn phải biết rằng việc mở rộng đòi hỏi phải sao chép lại mảng, việc này rất tốn thời gian.

Điều quan trọng là một nhược điểm khác của mảng là nếu bây giờ có 5 triệu tờ tiền và bạn muốn xóa một tờ tiền ở giữa, bạn cần phải di chuyển tờ tiền 2,5 triệu về phía trước một khoảng trắng.

Khi điều này xảy ra, anh trai tôi gần như suy sụp tinh thần và vô cùng khó chịu. Sư phụ không nỡ nhìn anh trai tôi đau đớn như vậy nên ngày tôi vào trường sư phụ đã bắt tôi luyện tập nội công của đồng hồ dây chuyền, lúc đầu tôi không hiểu, sợ sư phụ sẽ như vậy. thiên vị và không dạy cho tôi nội công mạnh nhất của sư phụ.

Phải đến một ngày chứng kiến ​​sư huynh gần như phát điên vì dữ liệu di động, tôi mới hiểu được ý tốt của Sư Phụ. Từ đó trở đi, tôi chăm chỉ rèn luyện kỹ năng nội bộ “danh sách liên kết” và tiến bộ rõ rệt. Cả sư phụ và các anh đều khen ngợi tài năng của tôi.

Kỹ năng nội bộ của danh sách liên kết được chia thành ba cấp độ:

• Cấp độ đầu tiên được gọi là "danh sách liên kết một chiều". Tôi chỉ có một con trỏ quay lại, trỏ đến dữ liệu tiếp theo;
• Cấp độ thứ hai được gọi là "danh sách liên kết kép". Tôi có hai con trỏ, con trỏ sau trỏ đến dữ liệu tiếp theo và con trỏ trước trỏ đến dữ liệu trước đó.
• Cấp độ thứ ba được gọi là "cây nhị phân". Con trỏ lùi được loại bỏ và thay thế bằng con trỏ trái và phải.

Nhưng kỹ năng hiện tại của tôi vẫn chưa đạt đến cấp độ thứ ba, nhưng Sư phụ đã nói rằng tôi có tiềm năng này, và việc tôi có thể thành thạo các kỹ năng phép thuật chỉ là vấn đề thời gian.

Hãy like trước rồi đọc: Chuyên mục "Con đường thăng tiến của lập trình viên Java" đã được mở nguồn trên GitHub. Các bạn có tài khoản GitHub hãy đến và sắp xếp một ngôi sao! Hãy xem liệu chúng tôi có thể lọt vào danh sách xu hướng không.

Địa chỉ GitHub: https://github.com/itwanger/toBeBetterJavaer.

  。

2. Kỹ năng nội bộ của LinkedList

Được rồi, sau khi tỏ tình như thế này thì chắc mọi người cũng quen thuộc với tôi rồi. Vì vậy, tiếp theo tôi sẽ chỉ cho bạn phương pháp sức mạnh bên trong của tôi.

Phương thức sức mạnh bên trong của tôi chủ yếu là một lớp bên trong tĩnh riêng được gọi là Node, là một node.

lớp tĩnh riêng tư Node { mục E; Node tiếp theo; Node trước; Node(Node trước, phần tử E, Node tiếp theo) { mục này = phần tử; mục này = tiếp theo; mục này = trước; }}

Nó bao gồm ba phần:

• phần tử trên nút
• nút tiếp theo
• Nút trước

Để tôi vẽ một bức tranh cho bạn xem.

• Đối với nút đầu tiên, prev là null;
• Đối với nút cuối cùng, tiếp theo là null;
• Đối với các nút còn lại, prev trỏ đến nút trước và next trỏ đến nút tiếp theo.

Những kỹ năng nội tại của tôi rất đơn giản. Trên thực tế, tôi đã ghi nhớ chúng trong đầu. Nhưng Sư phụ bảo tôi hãy niệm thầm mỗi sáng khi thức dậy và mỗi tối khi đi ngủ. Mặc dù hơi buồn chán nhưng tôi luôn tuân theo lời dạy của Sư Phụ.

  。

3. Động thái của LinkedList

Giống như người anh em ArrayList của tôi, thủ thuật của tôi không gì khác hơn là "thêm, xóa, sửa và tìm kiếm". Trước đó, tất cả chúng ta đều phải khởi tạo.

Danh sách LinkedList = danh sách LinkedList mới();

Anh em khi khởi tạo thì size mặc định là 10, anh em cũng có thể chỉ định size theo số phần tử cần lưu trữ. Tôi không cần nó.

1) Nước đi 1: Tăng

Bạn có thể gọi phương thức add để thêm các phần tử:

list.add("Vua Im Lặng Hai");list.add("Vua Im Lặng Ba");list.add("Vua Bốn Im Lặng");

Phương thức add thực sự gọi phương thức linkLast:

public boolean add(E e) { linkLast(e); trả về true;}

linkLast, như tên cho thấy, là một liên kết ở cuối danh sách liên kết:

void linkLast(E e) { node cuối cùng l = cuối cùng; node cuối cùng newNode = node<> mới (l, e, null); last = newNode; nếu (l == null) first = newNode; nếu không thì l.next = newNode; size++; modCount++;}

• Khi thêm phần tử đầu tiên, cả phần tử đầu tiên và phần tử cuối cùng đều rỗng.
• Sau đó tạo một nút mới newNode, nút trước và nút tiếp theo cũng rỗng.
• Sau đó gán cả cuối cùng và đầu tiên cho newNode.

Tại thời điểm này, nó không thể được gọi là danh sách liên kết vì cả nút trước và nút sau đều bị hỏng.

• Khi thêm phần tử thứ hai, cả phần tử đầu tiên và phần tử cuối cùng đều trỏ đến nút đầu tiên.
• Sau đó, tạo một nút mới newNode, điểm trước của nó trỏ đến nút đầu tiên và nút tiếp theo là null.
• Sau đó gán giá trị tiếp theo của nút đầu tiên cho newNode.

Danh sách liên kết tại thời điểm này vẫn chưa đầy đủ.

• Khi thêm phần tử thứ ba, điểm đầu tiên đến nút đầu tiên và điểm cuối cùng đến nút cuối cùng.
• Sau đó tạo một nút mới newNode, nút trước của nó trỏ đến nút thứ hai và nút tiếp theo là rỗng.
• Sau đó gán giá trị tiếp theo của nút thứ hai cho newNode.

Danh sách liên kết lúc này đã hoàn tất.

Động thái bổ sung này của tôi cũng có thể phát triển thành hai động thái còn lại:

• Phương thức addFirst() thêm phần tử vào vị trí đầu tiên;
• Phương thức addLast() thêm các phần tử vào cuối.

AddFirst thực sự gọi linkFirst trong nội bộ:

công khai void addFirst(E e) { liên kếtFirst(e);}

linkFirst chịu trách nhiệm đặt nút mới làm nút đầu tiên và cập nhật nút tiếp theo của nút mới đầu tiên lên nút đầu tiên trước đó.

private void linkFirst(E e) { node cuối cùng f = đầu tiên; node cuối cùng newNode = node<> mới(null, e, f); đầu tiên = newNode; nếu (f == null) cuối cùng = newNode; nếu không thì f.prev = newNode; size++; modCount++;}

Cốt lõi của addLast thực sự tương tự như addFirst, vì vậy tôi để mọi người hiểu.

2) Bước 2: Xóa

Tôi đã xóa khá nhiều động thái:

• Remove(): xóa nút đầu tiên
• Remove(int): xóa nút tại vị trí đã chỉ định
• Remove(Object): xóa nút của phần tử đã chỉ định
• RemoveFirst(): xóa nút đầu tiên
• RemoveLast(): xóa nút cuối cùng

loại bỏ các cuộc gọi nội bộ getFirst, vì vậy hai bước di chuyển có tác dụng như nhau.

Remove(int) thực sự gọi phương thức hủy liên kết nội bộ.

công khai E xóa (int index) { kiểm tra ElementIndex (index); trả về hủy liên kết (node ​​(index));}

Phương thức hủy liên kết thực sự dễ hiểu. Nó cập nhật phần tiếp theo và phần trước của nút hiện tại, sau đó đặt phần tử trên nút hiện tại thành null.

E unlink(Node x) { // assert x != null; phần tử E cuối cùng = x.item; phần tử Node cuối cùng tiếp theo = x.next; phần tử Node cuối cùng trước = x.prev; if (prev == null) { đầu tiên = tiếp theo; } else { phần tử prev.next = tiếp theo; x.prev = null; } if (next == null) { phần tử cuối cùng = trước; } else { phần tử next.prev = trước; x.next = null; } x.item = null; size--; modCount++; return element;}

Remove(Object) cũng gọi phương thức hủy liên kết nội bộ, nhưng trước đó, nút nơi đặt phần tử phải được tìm thấy trước:

public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false;}

Điều này được chia thành hai loại trong nội bộ, một là khi phần tử là null, bạn phải sử dụng == để đánh giá; loại còn lại là khi phần tử không null, bạn phải sử dụng bằng để đánh giá. không thể sử dụng giá trị bằng để xác định giá trị rỗng và lỗi NPE sẽ được đưa ra.

RemoveFirst gọi nội bộ phương thức unlinkFirst:

công khai E removeFirst() { cuối cùng Node f = đầu tiên; nếu (f == null) ném mới NoSuchElementException(); trả về unlinkFirst(f);}

unlinkFirst chịu trách nhiệm hủy nút đầu tiên và đặt giá trị trước của nút sau thành null.

private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element;}

3) Nước đi thứ ba: Thay đổi

Phương thức set() có thể được gọi để cập nhật các phần tử:

list.set(0, "Vua Năm Im Lặng");

Chúng ta hãy xem phương thức set():

công khai E set(int index, E phần tử) { checkElementIndex(index); Node x = node(index); E oldVal = x.item; x.item = phần tử; trả về oldVal;}

Trước tiên, hãy kiểm tra chỉ số dưới đã chỉ định để xem liệu nó có nằm ngoài giới hạn hay không, sau đó tìm nút gốc dựa trên chỉ số dưới:

Nút nút(int index) { // khẳng định isElementIndex(index); nếu (index < (kích thước >> 1)) { Nút x = đầu tiên; đối với (int i = 0; i < index; i++) x = x.next; trả về x; } nếu không { Nút x = cuối cùng; đối với (int i = kích thước - 1; i > index; i--) x = x.prev; trả về x; }}

size >> 1: tức là dịch sang phải một vị trí, tương đương với việc chia cho 2. Đối với máy tính, việc dịch chuyển hiệu quả hơn phép chia vì dữ liệu được lưu trữ ở dạng nhị phân bên trong máy tính.

Nói cách khác, phương thức nút sẽ đưa ra phán đoán sơ bộ về chỉ số dưới. Nếu gần đến nửa đầu, nó sẽ bắt đầu duyệt từ chỉ số dưới 0; nếu gần đến nửa sau, nó sẽ bắt đầu duyệt từ cuối.

Rất dễ dàng tìm thấy nút có chỉ số dưới được chỉ định. Chỉ cần thay thế các phần tử của nút ban đầu bằng nút mới và nó sẽ ổn.

4) Nước đi 4: Kiểm tra

Các phương pháp tôi sử dụng để kiểm tra có thể được chia thành hai loại:

• indexOf(Object): Tìm vị trí của một phần tử
• get(int): Tìm phần tử ở vị trí nhất định

Có hai loại indexOf bên trong. Một là khi phần tử là null, == phải được sử dụng để đánh giá; loại kia là khi phần tử không null, thì phải sử dụng bằng để đánh giá. Vì không thể sử dụng giá trị bằng để xác định giá trị rỗng nên lỗi NPE sẽ được đưa ra.

public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = đầu tiên; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = đầu tiên; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1;}

Cốt lõi của phương thức get thực sự là phương thức nút. Điều này đã được giải thích trước đây và sẽ được bỏ qua ở đây.

công khai E lấy (int index) { checkElementIndex (index); trả về node (index).item;}

Trên thực tế, động thái này cũng có thể phát triển thành các kỹ thuật khác, chẳng hạn như:

• Phương thức getFirst() được sử dụng để lấy phần tử đầu tiên;
• Phương thức getLast() được sử dụng để lấy phần tử cuối cùng;
• Các phương thức poll() và pollFirst() được sử dụng để xóa và trả về phần tử đầu tiên (mặc dù hai phương thức này có tên khác nhau nhưng nội dung phương thức của chúng hoàn toàn giống nhau);
• Phương thức pollLast() được sử dụng để loại bỏ và trả về phần tử cuối cùng;
• Phương thức seekFirst() được sử dụng để trả về nhưng không xóa phần tử đầu tiên.

  。

4. Những thách thức của LinkedList

Thành thật mà nói, tôi không thực sự thích so sánh mình với đàn anh ArrayList, bởi vì mỗi người chúng tôi đều có nội lực khác nhau và không có ai cao hơn hay thấp hơn.

Mặc dù sư huynh thường gọi tôi là sư đệ nhưng thực ra chúng tôi khá hòa thuận. Nhưng tôi biết rằng trong mắt người ngoài, đồng môn, anh em sẽ luôn cạnh tranh với nhau.

Ví dụ như sự phức tạp về thời gian của hai chúng tôi khi thêm, xóa, sửa và kiểm tra.

Có lẽ đây là số phận, từ ngày tôi vào sư đoàn, cuộc tranh luận này chưa bao giờ dừng lại.

Dù người ngoài có nhìn chúng tôi như thế nào thì trong mắt tôi, tiền bối vẫn luôn là người anh cả, tôi tôn trọng anh ấy và anh ấy sẵn sàng bảo vệ tôi.

Được rồi, thế là xong cho LinkedList.

Nếu có thời gian rảnh rỗi, bạn nên xé danh sách liên kết bằng tay. Bạn có thể bắt đầu từ danh sách liên kết một chiều.

Tôi hy vọng bạn có thể thích nó và cho tôi một chút động lực để cập nhật. Tôi cũng sẽ tiếp tục cải thiện chất lượng và mang đến cho bạn nhiều bài viết và nội dung kỹ thuật cốt lõi hơn ~.

Đến đây là kết thúc bài viết về việc tìm hiểu mã nguồn của Java LinkedList dưới dạng võ thuật. Để biết thêm thông tin về Java LinkedList, vui lòng tìm kiếm các bài viết trước của tôi hoặc tiếp tục duyệt qua các bài viết liên quan bên dưới, mong các bạn sẽ ủng hộ tôi trong thời gian tới! .

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

Cuối cùng, bài viết tìm hiểu mã nguồn Java LinkedList dưới dạng võ thuật kết thúc tại đây. Nếu bạn muốn biết thêm về cách hiểu mã nguồn Java LinkedList dưới dạng võ thuật, vui lòng tìm kiếm các bài viết của CFSDN hoặc tiếp tục tìm hiểu. duyệt các bài viết liên quan tôi hy vọng bạn sẽ hỗ trợ tôi trong tương lai! .