배열과 리스트의 차이점, 여러 연결 리스트에 대해

차이점과 언제 사용해야 하는가

배열의 특징 

https://hyeonstorage.tistory.com/258

• 같은 자료형을 가진 변수를 저장
• 연속된 메모리 공간으로 되어있다 ->메모리 관리가 편하다.
• 인덱스를 이용 -> 검색이 용이
•  
• 단점
• 한 데이터를 삭제해도 배열은 연속되야하므로 공간이 남는다. -> 메모리 낭비
• 정적이므로 배열의 크기를 컴파일 이전에 정해야 함
• 컴파일 이후 배열의 크기를 변동 x

리스트의 특징

https://hyeonstorage.tistory.com/258

• 순서가 있는 데이터 집합
• 불연속적 메모리 공간 -> 메모리 관리의 편리
• 동적임, 인덱스가 없다
• 포인터를 통한 접근 -> 다음 데이터의 위치를 알고 있어 삽입, 삭제가 용이
•  
• 단점
• 검색 성능 안 좋음
• 포인터를 통해 다음 데이터를 가리키므로 추가적인 메모리 공간 발생.

언제 사용해야 하는가

배열 : 삽입 삭제가 적고 검색이 많을 때

리스트 : 삽입삭제가 많고 검색이 적을 때

 

배열은 메모리가 연속적(주소 값 + 4byte)이라 검색이 빠르고 , 리스트는 주소가 연속적이지 않고 하나하나 타고 가봐야 알 수 있다.

 

단일 연결 리스트, 원형 리스트, 이중연결리스트, 이중 원형 리스트

https://ledgku.tistory.com/42

https://udud0510.tistory.com/5

1. 단순 연결 리스트

• node가 다음 값만 가리킨다. -> 한 방향으로만 진행된다.
• 항목 탐색 시, 순차 탐색 필요

2. 원형 연결 리스트

• 시작 값 = 마지막 값  -> 마지막 부분 구별을 위해 last값이 필요
• last값은 리스트 출력 시 마지막을 알리는 역할, 항목 추가 기준이 된다.
• 리스트를 돌 때 무한루프를 주의하라

3. 이중 연결 리스트

• 단일 연결 리스트가 한 방향으로만 가니까 단점을 고치기 위해 탄생
• 두 개의 node가 서로를 바라봐서 양방향 진행 가능 -> 복잡함

4. 이중 원형 리스트

https://supark7.tistory.com/entry/%EC%9D%B4%EC%A4%91-%EC%9B%90%ED%98%95-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-Doubly-Circular-Linked-List

 

• 앞 뒤로 포인터를 가지고 있으면서 원형 구조를 가지는 리스트
• 단점은 공간을 많이 차지하고 코드가 복잡하다.