[ 자료구조 ] 리스트와 연결 리스트 공통점과 차이점 총정리

[  자료구조 ] 리스트와 연결 리스트 공통점과 차이점 총정리

 

리스트와 연결 리스트

 

리스트
-순서가 있는 데이터를 말한다
-리스트 자료에 대한 연산은 검색, 변경(삽입, 삭제)이다.
-스택과 큐는 리스트의 특수한 형태이다.

리스트 자료구조의 구현
-배열은 리스트 자료구조를 구현하는 방법이다.
-연결 리스트도 리스트를 구현하는 방법이다.

배열을 이용한 리스트 구현은 다음과 같은 장단점이 있다.
-연속된 기억 장소(장점)
-데이터의 중간에 삽입, 삭제 시 데이터 이동이 필요하다. (단점)
-데이터 크기가 수행 전(컴파일 때) 결정된다. (장점, 단점)
-컴파일 때 결정되기 때문에 정적인 기억 장소 할당이다. (장점, 단점)

 

스택 : insertfirst, deletefirst
큐 : insertlast, deletelast

 

배열 특징

구현 방법 : 배열로 선언 int list [N];
기억 장소 기억 장소 확보 : 프로그램 수행 전 (compile time), 정적 기억 장소로 할당, 기억 장소 N개로 시작함
기억 장소 연속성 : 연속된 기억 장소 할당
삽입과 삭제 알고리즘 : O(n)

 

연결 리스트 특징

 

구현 방법 : 연결 리스트 구조체 포인터로 선언 list_ptr ptr;
기억 장소 기억 장소 확보 : 프로그램 수행 후 (run time), 동적 기억 장소 할당, 기억 장소 1개로 시작해서 계속 추가해나감
기억 장소 연속성 : 기억 장소 힙(heap) 영역에서 임의로 할당함.
삽입과 삭제 알고리즘 : O(1), 연결 리스트는 포인터를 사용하기 때문에 데이터의 길이와 상관이 없다.

 

- 배열에서 기억 장소가 수행 전에 할당되는 경우 기억 장소 크기가 고정되고, 사용 여부에 관계없이 기억 장소를 확보한다.
-연결 리스트에서는 기억 장소가 흩어져있고 링크를 통해 연결을 해야 한다.
- 프로그래밍은 연결 리스트가 더 복잡하다.