자료구조 - 2. 리스트

리스트

특징

• 데이터를 나란히 저장한다.
• 데이터가 일직선으로 구성된 선형 구조다.

일반적으로 리스트 하면 배열을 의미하지만 구현방식에 따라 다음 두가지로 나뉜다.

순차리스트 : 배열을 기반으로 구현된 리스트 (=배열)

연결리스트 : 메모리의 동적할당을 기반으로 구현된 리스트

 

순차리스트 단점

• 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
• 삽입, 삭제의 과정에서 데이터의 이동이 매우 빈번히 일어난다. 복잡하다

순차리스트 장점

• 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한번에 참조가 가능하다.

연결리스트 장점

• 삽입이 간단하다.

연결리스트 단점

• 데이터를 참조하는데 시간이 오래걸린다. 최대 O(n)의 시간이 걸린다.

즉, 데이터의 크기가 고정되어있고 참조를 많이 하면 배열이 좋고, 데이터의 크기가 변하면서 삽입, 삭제를 많이하면 연결리스트가 더 사용하기 좋다.

 

순차리스트

연결리스트

어떻게 구현하느냐에 따라 tail이나 cur이 없을 수도 있다.

원형 연결리스트

구현 방식에 따라 head만 있을수도 tail만 있을 수도 있다.

양방향 연결리스트