자료구조 : 개념 :: Linked-List ( 연결된 리스트 )

연결리스트

Linked-List는 Array와는 다르게 유연하게 크기 변경이 가능한 자료구조를 말한다.
데이터를 자유롭게 삽입/삭제 할 수 있는 장점이 있다.

개요

 배열은 고정된 메모리 크기가 할당되고, 생성 시 순간의 필요량보다 넉넉한 메모리가 할당되고 
 이에 따라 메모리 낭비가 발생한다.

특징

+ 용량이 고정되지 않아 유연하게 삽입/삭제
+ 구조의 중간에 자료 삽입/삭제 용이 

- N번째 항목의 접근(탐색)에 O(n) 의 시간이 걸려 비효율적

구성

• 노드 : 연결 리스트의 단위요소
  - (1) 데이터 필드 : 데이터 값을 저장하는 변수 공간
  - (2) 링크 필드 : 다음 노드의 주소를 갖는 포인터 변수 공간

• 헤드 포인터 : 리스트의 맨 앞에서 가장 첫번째 노드를 가리키는 포인터(데이터x)
  
  

연결리스트는 개별 노드가 연결된 구조이다.
 
마지막 노드의 링크필드의 포인터 주소는 NULL을 가리킨다.

종류

• 단순 연결 리스트 (singly linked list)
  : 지나간 이전 노드는 다시 찾아갈 수 없음
  
  
• 원형 연결 리스트 (circular linked list)
  : 맨 뒤의 노드를 맨 앞 노드에 연결하여, 한바퀴 돌아서 이전 노드를 찾아갈 수 있음
  
  
• 이중 연결 리스트 (doubly linked list)
  : 한 노드 당 링크 필드를 앞뒤로 두 개를 두어, 현재 노드를 기준으로 previous Node, Next Node에 양방향으로 주소를 연결하여 역순 접근을 가능하게 한 리스트로 쌍방향 노드탐색 가능, but 유지보수의 어려움

단순 연결리스트 응용

1. 단순 연결된 스택 구현 ( Stack, using Singly Linked-List )
	-> 스택의 top이 연결리스트의 head pointer와 대응

2. 단순 연결 리스트 구현 ( Linked-List )

3. 단순 연결된 큐 구현 ( Queue, using Singly Linked-List )

이중 연결리스트 응용

1. 이중 연결된 덱 ( Dequeue, using Doubly Linked-List ) 
    -> 덱에서 deleteRear()를 수행할 때, rear가 한칸 앞으로 반시계 회전 해야 하는데 
    단순연결리스트로 구현된 덱은 직전 선행노드를 바로 알 수 없으므로 O(n)의 시간복잡도가 발생한다.
     따라서, 양방향으로 연결된 이중 연결 리스트를 사용하는것이 효율적이다.

원형 연결리스트 응용

1. 원형 연결된 큐 구현 (Queue, using Circular Linked-List)
	-> 원형 연결된 큐는 연결리스트의 head/tail 중 tail을 큐의 시작점으로 사용하는 것이,
    	rear와 front에 둘 다 한번에 접근할 수 있다는 점에서 효율적이다.