Study | 자료구조 배열과 링크드리스트

자료구조 배열과 링크드리스트

목차

1. 배열
2. 링크드리스트
3. 배열과 링크드리스트의 차이점

1. 배열(Array)

• 정적 자료구조
• 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조
• 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없음 → 해당 배열 크기 이상의 데이터를 저장할 수 없음
• 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 째문에, index를 통한 임의 접근이 가능 → 접근과 탐색에 용이함
• 저장시 주로 사용 Ex. 바구니(안의 정보는 일렬로 줄이 세워져 있음)

시간 복잡도

• 탐색 : O(1). 단, 접근하고자 하는 인덱스를 알고 있어야 한다. 순차적으로 탐색시에는 O(n).
• 삽입 / 삭제 :
  • 배열의 처음 또는 중간에 삽입 및 삭제 : O(n) (삽입 지점 이후의 데이터를 옮겨야 하기 때문)
  • 배열의 끝에 삽입 및 삭제 : O(1)

2. 링크드리스트(Linked List)

• 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조
  • 첫번째 노드 : head
  • 마지막 노드 : tail
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있음
• 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이함

• Tree 구조의 근간이 되는 자료구조

  시간 복잡도

  • 탐색 : O(n)
  • 삽입 / 삭제: 삽입과 삭제 자체는 O(1)이다.
    • 연결 리스트의 처음에 삽입/삭제 : O(1)
    • 연결 리스트의 중간에 삽입/삭제 : O(n) (탐색시간 소요)
    • 연결 리스트의 끝에 삽입/삭제 :
      • 끝을 가리키는 별도의 포인터를 갖는 경우 : O(1)
      • 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n) (탐색시간 소요)

1. 이중 연결 리스트
   • 전/후로 탐색이 가능한 구조
   • 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
   • 이중 연결 리스트의 노드는 데이터, 이전 노드의 주소와 다음 노드의 주소를 저장
   • 이중 연결 리스트에서는 얻고자 하는 데이터의 위치가 tail에 가깝다면 tail에서부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있음 Ex. 음악 플레이어 앱(이전 곡과 다음 곡이 연결), 포토샵의 history(이전 작업으로 돌아가기)

1. 원형 연결 리스트
   • 단순 연결 리스트의 마지막 노드가 null을 가리키는 게 아닌, 처음 노드를 가리키는 구조
     (head에서부터 순회를 반복적으로 진행하다보면 다시 처음으로 돌아오는 구조)
   • 이중 연결 리스트도 마지막 노드가 처음 노드를 가리키는 구조가 되면, 이를 이중 원형 연결 리스트라고 함
   • 모든 노드가 원의 형태를 이루면서 연결되어 있기 때문에 원형 연결 리스트에서는 사실상 머리와 꼬리의 구분이 없음

3. 배열과 링크드리스트의 차이점

배열	연결리스트
정적 자료구조	동적 자료구조
미리 정해진 크기	크기를 정할 필요 X
연속된 메모리 주소 할당받음	연속된 메모리 주소 할당 X
접근, 탐색 용이	추가, 삭제 용이
index 존재	node 존재

---

출처

배열과 링크드리스트
배열과 링크드리스트 + 이중, 원형
이중 연결 리스트