[자료구조] 01. Array(배열)과 Linked List(연결 리스트)

<본 포스팅은 개인 공부 목적으로 작성되었습니다.>

✅ Array(배열)

배열은 가장 기본적인 자료구조로 같은 종류의 데이터를 순차적으로 저장한 데이터 구조로 논리적 저장순서와 물리적 저장순서가 같다. 인덱스로 해당 원소에 접근이 가능하며, 인덱스를 알고 있다면 O(1)의 시간 복잡도로 원소에 접근이 가능하다.

✔기본구조 및 용어

• Index(인덱스) : 데이터에 접근하기 위한 숫자로, 0부터 시작한다.
• Value : 해당 인덱스에 있는 데이터 값이다.

출처 - https://www.geeksforgeeks.org/c-sharp-arrays/

✔ 장단점

장점

• 인덱스 번호로 빠른 접근이 가능하다.
  • O(1)의 시간복잡도로 접근이 가능하다.

단점

• 데이터의 추가 및 삭제가 어렵다.
  • 순차적으로 저장이 되어있기 때문에 중간에 추가 및 삭제를 하면 뒤에 있는 데이터들을 한 칸씩 다 shift해줘야 한다. 그 과정에서 추가 cost가 발생한다.
  • 따라서 O(n)의 시간복잡도를 가진다.
• 배열의 크기가 정적이다.

 

✅ LinkedList(연결리스트)

Array(배열)은 미리 사용할 공간을 할당해야 한다. 이러한 단점을 보완하기 위해 LinkedList(연결리스트)가 나왔다. Array(배열)은 순차적인 연결된 공간에 데이터를 저장하는 자료구조라면 LinkedList(연결리스트)는 떨어진 곳에 존재하는 데이터를 화살표로 연결하여 관리하는 자료구조이다. 따라서 논리적 저장순서와 물리적 저장순서가 다르다.

✔ 기본구조 및 용어

• Node(노드) : 데이터 저장 단위(데이터 값, 포인터)로 구성
• Pointer(포인터) : 노드 안에서 다음이나 이전의 데이터의 위치를 가지고 있는 공간

✔ 장단점

장점

• 미리 공간을 할당하지 않아도 된다.
  • 배열은 미리 데이터 공간을 할당해야 한다.
• 시간복잡도는 O(N)으로 배열과 같지만 배열보다는 빠르다.

단점

• 연결을 위한 별도의 데이터 공간이 필요하므로 저장 효율이 좋지 않다.
• Search시 논리적 저장순서와 물리적 저장순서가 같지 않기 때문에 맨 처음 데이터 부터 탐색해줘야한다.
  • 이 과정 때문에 중간 삽입이나 삭제시에도 원소를 찾기위한 시간 O(N)이 추가적으로 발생한다.
• 중간 데이터 삭제 시 앞, 뒤에 데이터 연결을 재구성하는 추가적인 작업이 필요하다.