[Data Structure] 4. 리스트

이 카테고리에 정리된 내용은 강의시간에 필기한 내용이 주를 이룹니다. 교수님께서 강의 하신 내용들 중에 핵심들과 부가적인 내용들을 요약하여 게시했습니다. 강의시간에 생능출판사의 C언어로 쉽게 풀어쓴 자료구조 책을 사용했기 때문에 정리하는 순서도 이 책의 순서에 따라 하기로 했습니다. 순전히 정리용이기 때문에 시험기간이나 복습용으로는 적절하지만 순수한 학습용으로는 적절하지 않을 수 있습니다.

목록보기

 

4.1 리스트 추상 데이터 타입

– 리스트( list ) : 자료구조의 기본 형태. 순서에 입각한 상관 관계를 가짐.

 

4.2 배열로 구현된 리스트

– 연속적인 shift발생

 

4.3 연결 리스트

– 연결 리스트 : 연결된 표현. 삽입과 삭제 용이하고 연속된 shift가 필요 없음. 구현이 어렵다.

 

4.3.2 단순 연결 리스트

– 하나의 방향으로만 연결. 맨 마지막 노드는 NULL값을 가짐.

 

4.3.3 원형 연결 리스트

– 리스트의 마지막포인터에 헤드포인터를 연결.

– 한 노드에서 다른 모든 노드로의 접근이 가능.

 

4.3.4 이중 연결 리스트

– 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가짐.

– 헤드노드 : 리스트의 첫 번째 노드. 데이터를 가지지 않고 헤드를 알려주는 역할만 함. 삽입/삭제가 용이해짐.