자료구조 - Linked List

Linked List

연결된 목록은 각 요소가 별도의 개체 인 선형 데이터 구조 (예 : 배열)입니다. 

목록의 각 요소 (즉, 노드)는 데이터와 다음 노드에 대한 참조라는 두 항목으로 구성됩니다.

Types of Linked List :

1. 단독 링크 된 목록(Singly Linked List)

  : 이 유형의 연결 목록에서 모든 노드는 목록에 다음 노드의 주소 또는 참조를 저장하고 마지막 노드는 NULL로 다음 주소 또는 참조를 가집니다. 예 : 1-> 2-> 3-> 4-> NULL

2. 이중 링크 목록(Doubly Linked List)

 : 이 유형의 연결 목록에는 각 노드와 관련된 두 개의 참조가 있습니다. 하나는 다음 노드의 참조 지점이고 다른 하나는 이전 노드의 참조 지점입니다. 이 데이터 구조의 장점은 이전 노드에 명시 적으로 액세스 할 필요가없는 방향과 삭제를 모두 통과 할 수 있다는 것입니다. 예 : NULL <-1 <-> 2 <-> 3-> NULL

3. 순환 연결 목록(Circular Linked List)

 : 순환 연결 목록은 모든 노드가 연결되어 원을 형성하는 연결된 목록입니다. 끝에는 NULL이 없습니다. 순환 링크 목록은 단일 순환 링크 목록 또는 이중 순환 링크 목록이 될 수 있습니다. 이 데이터 구조의 장점은 모든 노드를 시작 노드로 만들 수 있다는 것입니다. 이것은 링크 된 목록에 순환 대기열을 구현할 때 유용합니다. 예 : 1-> 2-> 3-> 1 [마지막 노드의 다음 포인터가 첫 번째 포인터를 가리킴]

Accessing time of an element : O(n)
Search time of an element : O(n)
Insertion of an Element : O(1) [If we are at the position 
                                where we have to insert 
                                an element] 
Deletion of an Element : O(1) [If we know address of node
                               previous the node to be 
                               deleted] 

Example :  앞의 예제에서 우리가 학생 마크를 배열 한 것을 생각해보십시오. 이제 새로운 과목이 코스에 추가되면 마크도 배열에 추가됩니다. 그러나 배열의 크기가 고정되어 이미 채워져 있으므로 새로운 요소를 추가 할 수 없습니다. 피사체의 수보다 많은 크기의 배열을 만들면 배열의 대부분이 비어있을 가능성이 있습니다. 우리는 공간 낭비를 줄입니다. Linked List는 새로운 요소가 도입되었을 때만 노드를 추가합니다. 링크 된 목록을 사용하면 삽입 및 삭제 작업이 더욱 쉬워집니다. 
연결된 목록의 한 가지 큰 단점은 임의 액세스가 허용되지 않는다는 것입니다. 배열을 사용하면 O (1) 시간에 i 번째 요소에 액세스 할 수 있습니다. 연결된리스트에서 Θ (i) 시간이 걸립니다.