Tại sao phải chèn vào giữa danh sách được liên kết O (1)?

Question

Theo số Wikipedia article on linked lists, việc chèn vào giữa danh sách được liên kết được coi là O (1). Tôi nghĩ nó sẽ là O (n). Bạn sẽ không cần phải xác định vị trí các nút mà có thể được gần cuối danh sách?

Phân tích này không tính đến kết quả của hoạt động nút (mặc dù nó là bắt buộc) và chỉ cần chèn chính nó?

EDIT:

danh sách liên kết có nhiều lợi thế hơn mảng. Việc chèn một phần tử tại một điểm cụ thể của một danh sách là một hoạt động liên tục trong thời gian, trong khi việc chèn vào một mảng có thể yêu cầu di chuyển một nửa các phần tử, hoặc nhiều hơn.

Tuyên bố trên có một chút gây hiểu lầm cho tôi. Đúng tôi nếu tôi sai, nhưng tôi nghĩ rằng kết luận nên là:

Mảng:

• Tìm điểm chèn/xóa O (1)
• Thực hiện chèn/xóa O (n)

danh sách liên kết:

• Tìm điểm chèn/xóa O (n)
• Thực hiện O chèn/xóa (1)

Tôi nghĩ rằng thời gian duy nhất bạn sẽ không phải tìm vị trí là nếu bạn giữ một số loại con trỏ đến nó (như với đầu và đuôi trong một số trường hợp). Vì vậy, chúng tôi không thể nói thẳng rằng danh sách liên kết luôn đánh bại các mảng cho các tùy chọn chèn/xóa.

Answer 1

Bạn chính xác, bài viết xem xét "Lập chỉ mục" dưới dạng hoạt động riêng biệt. Vì vậy, chèn là chính nó O (1), nhưng nhận được rằng nút giữa là O (n).

Answer 2

Vì nó không liên quan đến bất kỳ vòng lặp nào.

Chèn giống như:

• yếu tố chèn
• liên kết để liên kết
• trước để tiếp
• làm

này là hằng số thời gian trong mọi trường hợp.

Do đó, chèn n thành phần sau cái kia là O (n).

Answer 3

Chèn là O (1) khi bạn biết bạn sẽ đặt nó ở đâu.

Answer 4

Không, khi bạn quyết định rằng bạn muốn chèn, giả sử bạn đang ở giữa đang lặp qua danh sách.

Thao tác trên Danh sách được liên kết thường được thực hiện theo cách không được coi là danh sách chung chung, nhưng dưới dạng tập hợp các nút - hãy nghĩ chính nút đó làm trình lặp cho vòng lặp chính của bạn. Vì vậy, khi bạn đang poking thông qua danh sách bạn nhận thấy như là một phần của logic kinh doanh của bạn mà một nút mới cần phải được thêm vào (hoặc một cái cũ đã bị xóa) và bạn làm như vậy. Bạn có thể thêm 50 nút trong một lần lặp.

Chỉnh sửa: Người đàn ông, bạn nhập đoạn thứ hai và đột nhiên thay vì là người trả lời đầu tiên, bạn là người thứ 5 nói giống như người đầu tiên 4!

Answer 5

Phân tích này không giải thích cho việc tìm kiếm hoạt động nút (mặc dù nó là bắt buộc) và chỉ cần chèn chính nó?

Bạn đã hiểu. Chèn tại một điểm nhất định giả định rằng bạn đã giữ con trỏ đến mục mà bạn muốn chèn sau:

InsertItem(item * newItem, item * afterItem) 

Answer 6

Bản thân chèn là O (1). Phát hiện nút là O (n).

Answer 7

Bài viết về cách so sánh các mảng với danh sách. Tìm vị trí chèn cho cả mảng và danh sách là O (N), vì vậy bài viết bỏ qua nó.

Answer 8

O (1) tùy thuộc vào thực tế rằng bạn có một mục mà bạn sẽ chèn mục mới. (trước hoặc sau). Nếu bạn không, đó là O (n) bởi vì bạn phải tìm mục đó.

Answer 9

Không, nó không tính đến việc tìm kiếm. Nhưng nếu bạn đã giữ một con trỏ đến một mục ở giữa danh sách, chèn vào thời điểm đó là O (1).

Nếu bạn phải tìm kiếm, bạn phải thêm vào thời gian tìm kiếm, sẽ là O (n).

Answer 10

Tôi nghĩ đây chỉ là trường hợp bạn chọn để tính cho ký hiệu O(). Trong trường hợp chèn hoạt động bình thường để đếm là hoạt động sao chép. Với một mảng, chèn vào giữa liên quan đến việc sao chép tất cả mọi thứ ở trên vị trí trong bộ nhớ. Với một danh sách liên kết, điều này sẽ trở thành thiết lập hai con trỏ. Bạn cần tìm vị trí bất kể cần chèn gì.

Answer 11

Để so sánh với một mảng, biểu đồ đó hiển thị, đó là O (1) vì bạn không phải di chuyển tất cả các mục sau nút mới.

Vì vậy, có, họ giả định rằng bạn đã có con trỏ đến nút đó, hoặc nhận được con trỏ là tầm thường. Nói cách khác, vấn đề được nêu: "nút đã cho tại X, mã sẽ chèn sau nút này là gì?" Bạn có thể bắt đầu tại điểm chèn.

Answer 12

Nếu bạn có tham chiếu của nút để chèn sau khi thao tác là O (1) cho danh sách được liên kết.
Đối với một mảng, nó vẫn là O (n) vì bạn phải di chuyển tất cả các nút hậu quả.

Answer 13

Các trường hợp phổ biến nhất có thể được chèn vào lúc bắt đầu hoặc ở cuối danh sách (và kết thúc danh sách có thể không mất thời gian để tìm).

Tương phản với việc chèn các mục ở đầu hoặc cuối của một mảng (yêu cầu thay đổi kích cỡ mảng nếu nó ở cuối hoặc thay đổi kích thước và di chuyển tất cả các phần tử nếu nó bắt đầu).

Answer 14

Việc chèn vào danh sách được liên kết khác với việc lặp lại trên danh sách đó.Bạn không định vị mục, bạn đang đặt lại con trỏ để đặt mục vào đó. Nó không quan trọng nếu nó sẽ được chèn vào gần cuối phía trước hoặc gần cuối, chèn vẫn liên quan đến con trỏ được phân công lại. Nó sẽ phụ thuộc vào cách nó được thực hiện, tất nhiên, nhưng đó là sức mạnh của danh sách - bạn có thể chèn một cách dễ dàng. Truy cập thông qua chỉ mục là nơi một mảng tỏa sáng. Tuy nhiên, đối với một danh sách, thông thường nó sẽ là O (n) để tìm mục thứ n. Ít nhất đó là những gì tôi nhớ từ trường học.