[CS 지식 - 자료구조] 배열, 동적배열, 연결 리스트

 

 

1. 배열(Array)

• 한 가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조
• 논리적 저장순서와 물리적 저장순서라 일치하는 자료구조
• 인덱스(Index)로 해당 원소에 접근 가능, Random Access가능
• 삽입/삭제 시 해당원소에 접근해 작업완료 후 공간이 생기지 않도록  shift해야하기 떄문에 O(N)의 시간 소요
• 장점
  - 각 데이터마다 Index를 부여하여 데이터 검색에 용이
• 단점
  - 배열의 크기가 고정적
  - 데이터가 삭제되면 배열 전체의 데이터를 재정렬

2. 동적 배열(Dynamic Array)

• 배열을 이용해 만들어 낸 별도의 자료구조
• 크기를 유동적으로 할 수 있고 메모리상에서 원소들이 연속적으로 붙어있어 인덱스 값을 이용해 랜덤접근 가능
• 장점
  - 배열의 크기 유동적
  - 메모리상에서 원소들이 연속적으로 붙어있어 인덱스 값을 이용해 린덤 접근가능
• 단점
  - 삽입/ 삭제 번거로움

3. 연결 리스트(Linked List)

• 노드와 포인터로 구성
• 각 데이터에 저장되어 있는 다음 데이터의 주소에 의해 연결되는 방식
• 데이터 물리적인 순서와 상관없이 포인터를 사용해 논리적인 순서대로 연결하는 구조
• 데이터 접근이 불리( O(N))
• 두개의 포인터를 가진 이중연결리스트(Double Linked List)존재
• 장점
  - 배열의 단점이 보완된 형태의 자료구조
    ▶ 크기가 가변적인 배열
    ▶ 효율적으로 메모리 사용가능
  - 데이터 삽입/ 삭제 용이
  - 물리적 순서를 맞추기 위한 오버헤드가 발생하지 않음
• 단점
  - 포인터를 통해 다음 노드를 참조하므로 추가적인 메모리 공간 발생
  - 임의의 데이터에 접근할 때 시간이 오래 걸림(순차 접근만 가능)

작업	배열	동적배열	연결리스트
검색	O(1)	O(1)	O(N)
삽입	O(N)	O(N)	O(N)
삭제	O(N)	O(N)	O(N)

 

▶▶ 데이터 접근(탐색, 조회)가 빈번 할 경우 : Array
▶▶ 데이터 수정(삽입, 삭제)이 빈번 할 경우 : Linked List

 

 

참고)
[자료구조] 연결 리스트 (Linked List) (tistory.com)

[자료구조] 연결 리스트 (Linked List)

[Data Structure] 배열, 동적 배열, 연결 리스트(Array & Dynamic Array& Linked List) :: 코딩 공부 일지 (tistory.com)

[Data Structure] 배열, 동적 배열, 연결 리스트(Array & Dynamic Array& Linked List)

[CS 정리] 자료 구조(Data Structure) (velog.io)

[CS 정리] 자료 구조(Data Structure)