C++) 28. List

1) list 기본 형식

 

list의 기본 형식은 다음과 같습니다.

>>

---

2) 동작 원리

 

list의 기본 단위는 node입니다. node는 list의 종류에 따라 다음 node만 기억해 데이터를 연결하거나 이전 node와 다음 node모두를 기억해 데이터를 연결합니다.

 

① 단일 연결 리스트

: 하나의 노드가 다음 노드의 주소를 기억해 연결

 

② 이중 연결 리스트

: 하나의 노드가 전/후 노드의 주소를 기억해 연결

 

③ 원형 연결 리스트

: 처음 노드와 마지막 노드가 연결되어 있는 리스트

---

3) 중간 삽입 삭제

 

list는 데이터가 연속적으로 존재하지 않고 각각의 노드가 다음 혹은 이전 노드의 주소를 기억해 연결하는 구조이기 때문에 중간 삽입 삭제가 vector보다 수월하다고 할 수 있습니다.

 

중간 삽입할 경우 삽입하는 위치 이전 노드의 다음 주소를 삽입되는 노드를 가리키고 삽입하는 위치 이후 노드의 이전 노드의 주소를 삽입하는 노드의 주소로 변경만 해주면 됩니다.

 

삭제의 경우는 이전노드의 다음 주소를 삭제하는 노드의 다음 주소를 가리키게 하고 삭제되는 노드 다음 노드가 가리키는 이전 주소를 삭제되는 노드의 이전 주소를 가리키게 하면 되기 때문입니다.

---

4) 임의 접근

 

하지만 데이터가 연속적으로 존재하지 않으므로 임의의 데이터에 대한 접근이 vector보다 힘들다는 점이 있습니다.

 

임의의 데이터에 접근하려면 차례대로 데이터를 읽어나가야 하기 때문입니다.

---

5) 간단한 예제

 

>>조사식

또한 list도 iterator를 지원합니다.

 

>>콘솔창 출력