연결 목록은 어떤 상황에서 유용합니까?

연결 목록은 어떤 상황에서 유용합니까?

---

대부분의 경우 사람들이 연결 목록을 사용하려고 시도하는 것은 나에게 좋지 않은 (또는 매우 가난한) 선택처럼 보입니다. 연결된 목록이 데이터 구조의 좋은 선택인지 아닌지에 대한 상황을 탐색하는 것이 유용 할 수 있습니다.

이상적으로는 데이터 구조를 선택하는 데 사용할 기준과 지정된 상황에서 가장 잘 작동 할 수있는 데이터 구조에 대한 답변이 설명됩니다.

편집 : 나는 숫자뿐만 아니라 답변의 질에 매우 감동했습니다. 나는 하나만 받아 들일 수 있지만 조금 더 나은 것이 없었다면 받아 들일 가치가 있었을 것이라고 말해야 할 두세 가지가 더 있습니다. 단 몇 명 (특히 내가 받아들이기로 한 사람)만이 연결 목록이 실질적인 이점을 제공하는 상황을 지적했습니다. 나는 Steve Jessop이 하나가 아니라 세 가지 다른 답변을 내놓은 것에 대해 일종의 명예로운 언급을 할 가치가 있다고 생각합니다. 물론 답변이 아닌 댓글로만 게시 되었음에도 불구하고 Neil의 블로그 항목도 읽을만한 가치가 있다고 생각합니다. 유익 할뿐만 아니라 재미도 있습니다.

---

동시 데이터 구조에 유용 할 수 있습니다. (이제 아래에 비 동시 실제 사용 샘플이 있습니다 . @Neil 이 FORTRAN을 언급하지 않았다면 존재하지 않을 것 입니다. ;-)

예를 들어 ConcurrentDictionary<TKey, TValue>.NET 4.0 RC에서는 연결 목록을 사용하여 동일한 버킷에 해시되는 항목을 연결합니다.

의 기본 데이터 구조 ConcurrentStack<T>도 링크 된 목록입니다.

ConcurrentStack<T>새로운 스레드 풀 의 기반 역할을하는 데이터 구조 중 하나입니다 (기본적으로 로컬 "큐"가 스택으로 구현 됨). (다른 주요지지 구조는 ConcurrentQueue<T>입니다.)

새로운 Thread Pool은 새로운 Task Parallel Library 의 작업 스케줄링을위한 기반을 제공합니다 .

따라서 그것들은 확실히 유용 할 수 있습니다. 연결 목록은 현재 적어도 하나의 훌륭한 신기술의 주요 지원 구조 중 하나입니다.

(단일 링크 된 목록은 주요 작업을 단일 CAS (+ 재시도) 로 수행 할 수 있기 때문에 이러한 경우에 잠금 없는 ( 잠금 없는 상태가 아닌) 매력적인 선택이됩니다 . 최신 GC-d 환경에서-예 : Java 및 .NET- ABA 문제 는 쉽게 피할 수 있습니다. 새로 생성 된 노드에 추가 한 항목을 랩핑하고 해당 노드를 재사용하지 마십시오. GC가 작업을 수행하도록합니다. ABA 문제에 대한 페이지는 잠금 구현도 제공합니다. 무료 스택-실제로 항목을 보유하는 (GC-ed) 노드가있는 .Net (& Java)에서 작동합니다.)

편집 : @Neil : 실제로 FORTRAN에 대해 언급 한 내용은 .NET에서 가장 많이 사용되고 남용되는 데이터 구조 인 일반 .NET generic에서 동일한 종류의 연결 목록을 찾을 수 있음을 상기시켜주었습니다 Dictionary<TKey, TValue>.

하나는 아니지만 많은 연결 목록이 배열에 저장됩니다.

• 삽입 / 삭제시 많은 소규모 (비) 할당을 수행하지 않습니다.
• 배열이 순차적으로 채워지기 때문에 해시 테이블의 초기로드는 매우 빠릅니다 (CPU 캐시로 매우 잘 재생 됨).
• 체이닝 해시 테이블은 메모리 측면에서 비싸다는 것은 말할 것도없고,이 "트릭"은 x64에서 "포인터 크기"를 절반으로 줄입니다.

기본적으로 많은 연결 목록이 배열에 저장됩니다. (사용 된 각 버킷에 대해 하나씩) 재사용 가능한 노드의 무료 목록은 그들 사이에 "혼합"됩니다 (삭제가있는 경우). 배열은 시작 / 재해시시 할당되고 체인 노드는 그 안에 보관됩니다. 삭제를 따르는 자유 포인터 (배열에 대한 인덱스 )도 있습니다 . ;-) 그래서-믿거 나 말거나-FORTRAN 기술은 여전히 ​​존재합니다. (... 그리고 가장 일반적으로 사용되는 .NET 데이터 구조 중 하나보다 다른 곳은 없습니다 ;-).

---

링크 된 목록은 임의의 (컴파일시 알 수없는) 길이의 목록에서 많은 삽입 및 제거를 수행해야하지만 너무 많이 검색하지 않아야 할 때 매우 유용합니다.

목록 분할 및 결합 (양방향 연결)은 매우 효율적입니다.

또한 연결 목록을 결합 할 수도 있습니다. 예를 들어 트리 구조는 수평 연결 목록 (형제)을 함께 연결하는 "수직"연결 목록 (상위 / 하위 관계)으로 구현 될 수 있습니다.

이러한 목적으로 배열 기반 목록을 사용하면 심각한 제한이 있습니다.

• 새 항목을 추가하면 어레이를 재 할당해야합니다 (또는 향후 확장을 허용하고 재 할당 횟수를 줄이는 데 필요한 것보다 더 많은 공간을 할당해야 함).
• 항목을 제거하면 공간이 낭비되거나 재 할당이 필요합니다.
• 끝을 제외한 모든 곳에 항목을 삽입하려면 많은 데이터를 한 위치 위로 복사 (재 할당 및)해야합니다.

---

연결된 목록은 매우 유연합니다. 하나의 포인터를 수정하면 배열 목록에서 동일한 작업이 매우 비효율적 인 경우 대규모 변경을 수행 할 수 있습니다.

---

배열은 연결된 목록이 일반적으로 비교되는 데이터 구조입니다.

일반적으로 연결된 목록은 목록 자체를 많이 수정해야 할 때 유용하지만 배열은 직접 요소 액세스의 목록보다 성능이 좋습니다.

다음은 상대 작업 비용 (n = 목록 / 배열 길이)과 비교하여 목록 및 배열에서 수행 할 수있는 작업 목록입니다.

• 요소 추가 :
  • 목록에서 새 요소에 대한 메모리를 할당하고 포인터를 리디렉션하면됩니다. O (1)
  • 어레이에서는 어레이를 재배치해야합니다. 의 위에)
• 요소 제거
  • 목록에서 포인터를 리디렉션합니다. O (1).
  • 배열에서 제거 할 요소가 배열의 첫 번째 또는 마지막 요소가 아닌 경우 배열을 재배치하는 데 O (n) 시간을 소비합니다. 그렇지 않으면 단순히 포인터를 배열의 시작으로 재배치하거나 배열 길이를 줄일 수 있습니다.
• 알려진 위치에서 요소 가져 오기 :
  • 목록에서 첫 번째 요소에서 특정 위치의 요소로 목록을 걸어야합니다. 최악의 경우 : O (n)
  • 배열에서 요소에 즉시 액세스 할 수 있습니다. O (1)

이것은이 두 가지 인기 있고 기본적인 데이터 구조에 대한 매우 낮은 수준의 비교이며 목록 자체를 많이 수정해야하는 상황에서 목록이 더 잘 수행된다는 것을 알 수 있습니다 (요소 제거 또는 추가). 반면에 배열의 요소에 직접 액세스해야하는 경우 배열이 목록보다 성능이 좋습니다.

메모리 할당의 관점에서 볼 때 모든 요소를 ​​나란히 둘 필요가 없기 때문에 목록이 더 좋습니다. 반면에 다음 (또는 이전) 요소에 대한 포인터를 저장하는 데는 약간의 오버 헤드가 있습니다.

이러한 차이점을 아는 것은 개발자가 구현에서 목록과 배열 중에서 선택하는 데 중요합니다.

이것은 목록과 배열의 비교입니다. 여기에보고 된 문제에 대한 좋은 해결책이 있습니다 (예 : SkipLists, Dynamic Arrays 등). 이 답변에서는 모든 프로그래머가 알아야 할 기본 데이터 구조를 고려했습니다.

---

단일 연결 목록은 셀 할당 자 또는 개체 풀의 사용 가능한 목록에 적합합니다.

1. 스택 만 필요하므로 단일 연결 목록이면 충분합니다.
2. 모든 것이 이미 노드로 나뉩니다. 셀이 포인터를 포함 할만큼 충분히 큰 경우 침입 목록 노드에 대한 할당 오버 헤드가 없습니다.
3. A vector or deque would impose an overhead of one pointer per block. This is significant given that when you first create the heap, all cells are free, so it's an up-front cost. In the worst case it doubles the memory requirement per cell.

---

Doubly-linked list is a good choice to define the ordering of a hashmap which also defines an order on the elements (LinkedHashMap in Java), especially when ordered by last access:

1. More memory overhead than an associated vector or deque (2 pointers instead of 1), but better insert/remove performance.
2. No allocation overhead, since you need a node for a hash entry anyway.
3. Locality of reference is no additional problem compared with a vector or deque of pointers, since you'd have to pull each object into memory either way.

Sure, you can argue about whether an LRU cache is a good idea in the first place, compared with something more sophisticated and tuneable, but if you're going to have one, this is a fairly decent implementation. You do not want to perform a delete-from-middle-and-add-to-the-end on a vector or deque at every read access, but moving a node to the tail is typically fine.

---

They're useful when you need high-speed push, pop and rotate, and don't mind O(n) indexing.

---

Singly-linked lists are the obvious implementation of the common "list" data type in functional programming languages:

1. Adding to the head is fast, and (append (list x) (L)) and (append (list y) (L)) can share almost all of their data. No need for copy-on-write in a language with no writes. Functional programmers know how to take advantage of this.
2. Adding to the tail is unfortunately slow, but so would be any other implementation.

By comparison, a vector or deque would typically be slow to add at either end, requiring (at least in my example of two distinct appends) that a copy be taken of the entire list (vector), or the index block and the data block being appended to (deque). Actually, there may be something to be said there for deque on large lists which do need to add at the tail for some reason, I'm not sufficiently informed about functional programming to judge.

---

Linked lists are one of the natural choices when you cannot control where your data is stored, but you still need to somehow get from one object to the next.

For example when implementing memory tracking in C++ (new/delete replacement) you either need some control data structure that keeps track of which pointers have been freed, which you fully need to implement yourself. The alternative is to overallocate and add a linked list to the beginning of each data chunk.

Because you always imediately know, where you are in the list when delete is called, you can easily give up memory in O(1). Also adding a new chunk that has just been malloced is in O(1). Walking the list is very rarely needed in this case, so the O(n) cost is not an issue here (walking a structure is O(n) anyway).

---

From my experience, implementing sparse-matrices and fibonacci heaps. Linked lists give you more control over the overall structure for such data structures. Though I'm not sure if sparse-matrices are best implemented using linked lists - probably there is a better way, but it really helped learning the ins-and-outs of sparse matrices using linked lists in undergrad CS :)

---

One example of good usage for a linked list is where the list elements are very large ie. large enough that only one or two can fit in CPU cache at the same time. At this point the advantage that contiguous block containers like vectors or arrays for iteration have is more or less nullified, and a performance advantage may be possible if many insertions and removals are occurring in realtime.

---

Consider that a linked list might be very useful in a Domain Driven Design style implementation of a system that includes parts that interlock with repetition.

An example that comes to mind might be if you were to be modelling a hanging chain. If you wanted to know what the tension on any particular link was, your interface could include a getter for "apparent" weight. The implementation of which would include a link asking its next link for its apparent weight, then adding its own weight to the result. This way, the whole length down to the bottom would be evaluated with a single call from the chain's client.

Being a proponent of code that reads like natural language, I like how this would let the programmer ask a chain link how much weight it's carrying. It also keeps the concern of calculating these kids of properties within the boundary of the link implementation, removing the need for a chain weight calculating service".

---

One of the most useful cases I find for linked lists working in performance-critical fields like mesh and image processing, physics engines, and raytracing is when using linked lists actually improves locality of reference and reduces heap allocations and sometimes even reduces memory use compared to the straightforward alternatives.

Now that can seem like a complete oxymoron that linked lists could do all that since they're notorious for often doing the opposite, but they have a unique property in that each list node has a fixed size and alignment requirements which we can exploit to allow them to be stored contiguously and removed in constant-time in ways that variable-sized things cannot.

As a result, let's take a case where we want to do the analogical equivalent of storing a variable-length sequence which contains a million nested variable-length sub-sequences. A concrete example is an indexed mesh storing a million polygons (some triangles, some quads, some pentagons, some hexagons, etc) and sometimes polygons are removed from anywhere in the mesh and sometimes polygons are rebuilt to insert a vertex to an existing polygon or remove one. In that case, if we store a million tiny std::vectors, then we end up facing a heap allocation for every single vector as well as potentially explosive memory use. A million tiny SmallVectors might not suffer this problem as much in common cases, but then their preallocated buffer which isn't separately heap-allocated might still cause explosive memory use.

The problem here is that a million std::vector instances would be trying to store a million variable-length things. Variable-length things tend to want a heap allocation since they cannot very effectively be stored contiguously and removed in constant-time (at least in a straightforward way without a very complex allocator) if they didn't store their contents elsewhere on the heap.

If, instead, we do this:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

... then we've dramatically reduced the number of heap allocations and cache misses. Instead of requiring a heap allocation and potentially compulsory cache misses for every single polygon we access, we now only require that heap allocation when one of the two vectors stored in the entire mesh exceeds their capacity (an amortized cost). And while the stride to get from one vertex to the next might still cause its share of cache misses, it's still often less than if every single polygon stored a separate dynamic array since the nodes are stored contiguously and there's a probability that a neighboring vertex might be accessed prior to eviction (especially considering that many polygons will add their vertices all at once which makes the lion's share of polygon vertices perfectly contiguous).

Here is another example:

... where the grid cells are used to accelerate particle-particle collision for, say, 16 million particles moving every single frame. In that particle grid example, using linked lists we can move a particle from one grid cell to another by just changing 3 indices. Erasing from a vector and pushing back to another can be considerably more expensive and introduce more heap allocations. The linked lists also reduce the memory of a cell down to 32-bits. A vector, depending on implementation, can preallocate its dynamic array to the point where it can take 32 bytes for an empty vector. If we have around a million grid cells, that's quite a difference.

... and this is where I find linked lists most useful these days, and I specifically find the "indexed linked list" variety useful since 32-bit indices halve the memory requirements of the links on 64-bit machines and they imply that the nodes are stored contiguously in an array.

Often I also combine them with indexed free lists to allow constant-time removals and insertions anywhere:

In that case, the next index either points to the next free index if the node has been removed or the next used index if the node has not been removed.

And this is the number one use case I find for linked lists these days. When we want to store, say, a million variable-length sub-sequences averaging, say, 4 elements each (but sometimes with elements being removed and added to one of these sub-sequences), the linked list allows us to store 4 million linked list nodes contiguously instead of 1 million containers which are each individually heap-allocated: one giant vector, i.e., not a million small ones.

---

I have used linked lists (even doubly linked lists) in the past in a C/C++ application. This was prior to .NET and even stl.

I probably wouldn't use a linked list now in a .NET language because all the traversal code you need is provided for you via the Linq extension methods.

---

There are two complementary operations which are trivially O(1) on lists and very hard to implement in O(1) in other data structures - removing and inserting an element from arbitrary position, assuming you need to maintain the order of elements.

Hash maps can obviously do insertion and deletion in O(1) but then you cannot iterate over the elements in order.

Given the fact above, hash map can be combined with a linked list to create a nifty LRU cache: A map that stores a fixed number of key-value pairs and drops the least recently accessed key to make room for new ones.

The entries in the hash map need to have pointers to the linked list nodes. When accessing the hash map, the linked list node is unlinked from its current position and moved to the head of the list (O(1), yay for linked lists!). When there's need to remove the least recently used element, the one from the tail of the list needs to be dropped (again O(1) assuming you keep the pointer to the tail node) together with the associated hash map entry (so backlinks from the list to the hash map are necessary.)

참고URL : https://stackoverflow.com/questions/2429217/under-what-circumstances-are-linked-lists-useful