Cấu trúc dữ liệu có O (1) để nối thêm, thêm vào và lấy phần tử ở bất kỳ vị trí nào?

Question

Tôi đang tìm giải pháp Java nhưng mọi câu trả lời chung đều OK.

Vector/ArrayList là O (1) để nối và truy xuất, nhưng O (n) để thêm vào.

LinkedList (trong Java được thực hiện dưới dạng danh sách liên kết kép) là O (1) để nối và thêm vào, nhưng O (n) để truy xuất.

Deque (ArrayDeque) là O (1) cho mọi thứ ở trên nhưng không thể truy xuất phần tử ở chỉ mục tùy ý. Trong tâm trí của tôi, cấu trúc dữ liệu đáp ứng yêu cầu ở trên có 2 danh sách có thể phát triển bên trong (một cho phần thêm và một cho chắp thêm) và cũng lưu giữ một bù để xác định nơi lấy phần tử trong quá trình truy xuất.

Answer 1

Bạn đang tìm hàng đợi gấp đôi. Điều này được thực hiện theo cách bạn muốn trong C++ STL, đó là bạn có thể lập chỉ mục vào nó, nhưng không phải trong Java, như bạn đã lưu ý. Bạn có thể hình dung cuộn của riêng bạn từ các thành phần tiêu chuẩn bằng cách sử dụng hai mảng và lưu trữ ở đâu "không". Điều này có thể lãng phí bộ nhớ nếu bạn kết thúc di chuyển một chặng đường dài từ số không, nhưng nếu bạn nhận được quá xa bạn có thể rebase và cho phép deque để thu thập dữ liệu vào một mảng mới.

Một giải pháp thanh lịch hơn không thực sự đòi hỏi quá nhiều fanciness trong việc quản lý hai mảng là áp đặt một mảng tròn lên một mảng được phân bổ trước. Điều này sẽ yêu cầu thực hiện push_front, push_back, và thay đổi kích thước của mảng đằng sau nó, nhưng các điều kiện để thay đổi kích thước và như vậy sẽ sạch hơn nhiều.

Answer 2

Ý tưởng của bạn có thể hoạt động. Nếu đó là những thao tác duy nhất bạn cần hỗ trợ, thì hai Vectơ là tất cả những gì bạn cần (gọi chúng là Head và Tail). Để thêm vào, bạn nối thêm vào đầu và để nối thêm, bạn nối đuôi. Để truy cập một phần tử, nếu chỉ số nhỏ hơn head.Length, sau đó trả về phần đầu [head.Length-1-index], ngược lại là đuôi [index-head.Length]. Tất cả các hoạt động này rõ ràng là O (1).

Answer 3

Nếu bạn đối xử thêm vào sau một Vector/ArrayList là O (1) - mà nó thực sự là không, nhưng có thể đủ gần trong thực tế -
(EDIT - để làm rõ - append có thể khấu hao theo thời gian liên tục , đó là - trên trung bình, việc bổ sung sẽ là O (1), nhưng có thể hơi tồi tệ hơn về gai. Tùy thuộc vào ngữ cảnh và các hằng số chính xác có liên quan, hành vi này có thể gây chết người).

(Đây không phải là Java, nhưng một số ngôn ngữ được tạo sẵn ...).

Một vectơ sẽ được gọi là "Chuyển tiếp". Vectơ thứ hai sẽ được gọi là "Lùi lại".

Khi được yêu cầu chắp thêm - Forward.Append().

Khi được yêu cầu thêm - Backwards.Append().

Khi được yêu cầu truy vấn -

if (Index < Backwards.Size()) 
{ 
    return Backwards[ Backwards.Size() - Index - 1 ] 
} 
else 
{ 
    return Forward[ Index - Backwards.Size() ] 
} 

(và cũng có thể kiểm tra các chỉ số là ngoài giới hạn).

Answer 4

Những gì bạn muốn là hàng đợi đôi (deque) giống như STL, vì Java ArrayDeque thiếu get() vì một số lý do.Có một số gợi ý tốt và liên kết đến triển khai ở đây:

• Java equivalent of std::deque?

Answer 5

Một deque (double-ended queue) có thể được thực hiện để cung cấp tất cả các hoạt động này trong thời gian O (1) thời gian, mặc dù không phải tất cả các triển khai đều làm. Tôi đã không bao giờ sử dụng ArrayDeque của Java, vì vậy tôi nghĩ bạn đã nói đùa về nó không hỗ trợ truy cập ngẫu nhiên, nhưng bạn hoàn toàn đúng - như là một deque "thuần túy", nó chỉ cho phép truy cập dễ dàng ở hai đầu. Tôi có thể thấy lý do tại sao, nhưng điều đó chắc chắn gây phiền nhiễu ...

Với tôi, cách lý tưởng để thực hiện một deque cực nhanh là sử dụng circular buffer, đặc biệt vì bạn chỉ quan tâm đến việc thêm loại bỏ ở mặt trước và mặt sau. Tôi không nhận ra ngay lập tức một trong Java, nhưng tôi đã viết một cái trong Objective-C như là một phần của một khung công tác nguồn mở. Bạn được quyền sử dụng mã, hoặc là như hoặc là một mẫu để thực hiện của riêng bạn.

Đây là WebSVN portal to the code và related documentation. Thịt thật nằm trong tệp CHAbstractCircularBufferCollection.m - tìm kiếm các phương pháp appendObject: và prependObject:. Thậm chí còn có một điều tra viên tùy chỉnh ("trình lặp" trong Java) được định nghĩa là tốt. Logic đệm tròn cần thiết là khá tầm thường, và được thể hiện trong những 3 trung #define macro:

#define transformIndex(index) ((headIndex + index) % arrayCapacity) 
#define incrementIndex(index) (index = (index + 1) % arrayCapacity) 
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1) 

Như bạn có thể thấy trong các phương pháp objectAtIndex:, tất cả các bạn làm để truy cập vào các yếu tố thứ N trong một deque là array[transformIndex(N)]. Lưu ý rằng tôi thực hiện tailIndex luôn trỏ đến một vị trí ngoài phần tử được lưu trữ cuối cùng, vì vậy nếu headIndex == tailIndex, mảng đầy hoặc trống nếu kích thước là 0,

Hy vọng điều đó sẽ hữu ích. Xin lỗi vì đã đăng mã không phải Java, nhưng tác giả câu hỏi đã làm nói rằng các câu trả lời chung có thể chấp nhận được.

Answer 6

Đây là cấu trúc dữ liệu hỗ trợ O (1) nối thêm, thêm vào, đầu tiên, cuối cùng và kích thước. Chúng ta có thể dễ dàng thêm các phương pháp khác từ AbstractList<A> như delete và update

import java.util.ArrayList; 

public class FastAppendArrayList<A> { 
    private ArrayList<A> appends = new ArrayList<A>(); 
    private ArrayList<A> prepends = new ArrayList<A>(); 

    public void append(A element) { 
     appends.add(element); 
    } 

    public void prepend(A element) { 
     prepends.add(element); 
    } 

    public A get(int index) { 
     int i = prepends.size() - index; 
     return i >= 0 ? prepends.get(i) : appends.get(index + prepends.size()); 
    } 

    public int size() { 
     return prepends.size() + appends.size(); 
    } 

    public A first() { 
     return prepends.isEmpty() ? appends.get(0) : prepends.get(prepends.size()); 
    } 

    public A last() { 
     return appends.isEmpty() ? prepends.get(0) : appends.get(prepends.size()); 
    }