리스트
배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당 되므로
리스트의 순차적 표현(sequential representation)이라고 한다.
- 장점 : 빠름
- 단점 : 크기가 고정됨
연결리스트
연결 리스트는 포인터를 사용하여 데이터를 연결한다.
(동적으로 공간 확보)
장점
- 크기 제한이 없다.
- 중간에서도 쉽게 삽입 삭제가 가능하다.
단점
- 구현이 복잡하다.
- 임의의 항목을 추출할 때 배열보다 오래걸림
- 포인터도 저장하여야 하므로 메모리 공간 많이 차지
하나의 프로그램에서 여러 연결리스트들은 첫번째 데이터로 구별
즉 첫번째 데이터만 알 수 있다면 연결 리스트의 나머지 데이터도 알 수 있다.
자기참조 구조체
자기참조 구조체란 자기 자신의 구조체를 가르키는 포인터를 포함하는 구조체를 의미한다.
원형 연결 리스트
중요 개념
- 원형 연결리스트에서 head는 마지막 노드
장점
- 하나의 노드에서 다른 모든 노드로 접근이 가능
- 노드의 삽입과 삭제가 단순 연결 리스트보다 용이
- 리스트의 끝에 노드를 삽입하는 연산이 효율적
응용
- 원형 연결리스트는 컴퓨터의 여러 응용프로그램을 하나의 CPU를 이용하여 실행할 때 필요하다.
- 멀티 플레이어 게임
이중 연결 리스트
이중 연결 리스트는 단순 연결 리스트에서는 선행 노드를 찾기 어렵다는 문제를
양방향으로 자유롭게 움직일 수 있게 보안하여 만들어진 자료구조이다.
장점
- 양방향으로 검색이 가능함(유용함)
단점
- 공간을 많이 차지하고 코드가 복잡함
- 실제 응용 프로그램에서는 이중 연결 리스트와 원형 연결 리스트를 혼합하여 많이 사용함
연결 리스트로 구현한 스택
- 크기가 제한되지 않는다는 큰 장점이 있다
- 하지만 배열 보다는 삽입 삭제 등 연산에 시간이 더 걸린다.
연결 리스트로 구현한 큐
- 마찬가지로 크기가 제한 되지 않는다.
- 하지만 코드가 복잡해지며 링크 필드 때문에 메모리 공간을 더 많이 차지한다.
