순차 리스트 / 연결 리스트

1. 순차 리스트

- 논리적인 순서와 물리적인 순서가 같은 구조.

- 메모리에 연속적으로 저장된다. ex) Array

- 구현이 비교적 간단하고, 인덱스를 사용하여 랜덤 액세스가 가능하다.

- 논리적인 순서와 물리적인 순서가 동일하기 때문에 삽입, 삭제가 되는 경우,

물리적인 순서를 논리적인 순서에 맞추기 위한 데이터의 이동이 필요하다.

(물리적인 순서를 맞추기 위한 오버헤드 발생)

- 예를 들어, 1 ~ 10 까지의 데이터를 저장하고 있는 순차 리스트가 있다고 가정한다.

 맨 앞의 1을 삭제한다면, 그 다음에 존재하는 2 ~ 9의 데이터가 하나씩 앞으로 당겨지는 이동이 발생한다.

 반대로 3과 4 사이에 데이터가 삽입된다면, 4 ~ 10의 데이터가 뒤로 하나씩 이동해야 하는 일이 발생한다.

2. 연결 리스트

- 각 노드에 저장된 다음 노드의 주소에 의해 연결된 구조.

- 메모리가 연속된 주소일 필요가 없기 때문에, 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.

- 주소에 의해 연결되기 때문에 삽입, 삭제에 용이하다.

- 순차 리스트에 비해, 길이가 가변적이다.

2-1. 단일 연결 리스트

- 하나의 노드는 데이터 필드와 링크 필드를 가지고 있다.

- 데이터 필드 : 데이터 저장 / 링크 필드 : 노드의 다음 주소를 저장

- 마지막 노드(테일)의 링크 필드는 null이다.

- 삽입 연산

1. 선행자의 링크 필드에 저장된 주소를 삽입할 노드의 링크 필드에 저장

2. 선행자의 링크 필드에 삽입할 노드의 주소를 저장

 => 예외 처리 : 선행자를 찾을 수 없는 경우

- 삭제 연산

1. 삭제할 노드의 링크 필드에 저장된 주소를 선행자의 링크 필드에 저장

2. 삭제할 노드를 삭제한다.

=> 예외 처리 : 삭제할 노드를 찾을 수 없는 경우

- 검색 연산

1. 헤드부터 탐색 시작

2. 노드의 링크 필드가 널일 때까지 탐색

3. 노드의 데이터 필드가 검색 데이터와 동일하면 탐색 중지

4. 해당 데이터의 노드 반환

=> 검색한 데이터가 리스트에 존재하지 않는 경우

(헤드부터 검색을 하기 때문에 최악의 경우 리스트를 전부 검색해야한다.)

2-2. 원형 연결 리스트

- 마지막 노드(테일)의 링크 필드에 헤드의 주소를 저장

- 리스트의 맨 앞에 노드를 삽입하는 경우, 테일의 링크 필드가 갱신되어야 한다.

2-3. 이중 연결 리스트

- 단일 연결 리스트나 원형 연결 리스트는 현재 노드의 이전 노드에 접근하기 위해서는 리스트를 한 번 순회해야 한다.

- 이점을 보완하여, 이전 노드의 주소를 저장한 것이 이중 연결 리스트이다.

- 링크 필드를 두 개 가지고 있다.

- 링크 필드 : Left Link Field(이전 노드의 주소 저장), Right Link Field(다음 노드의 주소 저장)

- 삽입 연산

1. 선행자의 Right Link Field에 저장된 주소를 삽입할 노드의 Right Link Field에 저장

2. 삽입할 노드의 Left Link Field에 선행자의 주소를 저장

3. 선행자의 다음 노드의 Left Link Field에 삽입할 노드의 주소를 저장

4. 선행자의 Right Link Field에 삽입할 노드의 주소를 저장

=> 예외 처리 : 선행자를 찾을 수 없는 경우

- 삭제 연산

1. 삭제할 노드의 이전 노드의 Right Link Field에 삭제할 노드의 Right Link Field에 저장된 주소 저장

2. 삭제할 노드의 다음 노드의 Left Link Field에 삭제할 노드의 Left Link Field에 저장된 주소 저장

=> 삭제할 노드의 이전 노드 또는 다음 노드가 null인 경우

- Single Linked List 구현

Github : https://github.com/LeeJiu/BasicStudy/tree/master/DataStructure/170418_SingleLinkedList