6장 연결 리스트

순차 선형 리스트는 논리적인 순서와 물리적이 순서가 같기 때문에 원소의 위치를 찾아 액세스하기 쉬우나, 삽인 삭제 후 원소들의 위치이동에서 많은 추가작업과 시간이 필요하다. 이러한 문제를 개선한 자료 표현 방식으로 연결자료구조(비순차 자료구조)가 있다.

 

연결자료구조는 노드를 사용하는데 노드는 데이터필드와 링크필드로 구성되어있다.

data(원소)

link(주소)

 

단순 연결 리스트

- 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결리스트

 

ex) 다음 연결리스트 월, 금 사이에 150[수][null]를 연결하려면

100 -> 100[월][200] -> 200[금][300] -> 300[일][null]

 

100 -> 100[월][150] -> 150[수][200] -> 200[금][300] -> 300[일][null]

 

 

 

자유 공간 리스트

- 연결리스트에서 삽입 연산을 하려면 먼저 메모리에서 공백 노드를 가져와야한다. 매 작업때마다 일일이 처리하는 대신에 미리 노드로 나누어서 연결해 놓은 리스트를 자유 공간 리스트 라고한다.

 

 

 

원형 연결 리스트

- 단순 연결 리스트에서 마지막 노드가 리스트이 첫 번째 노드를 가르키게 햐여 리스트의 구조를 원형으로 만든 연결 리스트를 원형 연결 리스트라 한다.

 

 

이중 연결 리스트

- 단순 연결 리스트에서 선행 노드에 접근하기가 어렵다는 점을 개선하여 원형 연결 리스트를 구성했지만, 원형 연결 리스트에서도 현재 노드의 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제가 있다. 링크가 한 방향으로만 순회하기때문에 이러한 문제가 발행하는데, 이를 개선하기 위해 양방향으로 순회가 가능한것이 이중 연결 리스트이다.

link

data

link

이중 연결 리스트 원소 삽입 방법 정리

1. 삽입할 노드를 가져온다

2. 새 노드의 데이터 필드에 값을 저장한다.

3. 새 노드의 왼쪽 노드의 오른쪽 링크를 새 노드의 오른쪽 링크에 저장한다.

4. 왼쪽 노드의 오른쪽 링크에 새 노드의 주소를 저장한다.

5. 새 노드의 오른쪽 노드의 왼쪽 링크를 새 노드의 왼쪽 링크에 저장한다.

6. 오른쪽 노드의 왼쪽 링크에 새 노드의 주소를 저장한다.