자료 구조란...2편 (배열과 연결 리스트)

들어가기 전

자료 구조 1편
1편에 이어서 2편 배열과 연결 리스트에 대해 공부해보자.

---

자료구조에는 여러 종류가 있으며, 이러한 각각의 자료구조는 각자의 연산 및 목적에 맞추어져 있다. 예를 들어 B-트리는 데이터베이스에 효율적이며, 라우팅 테이블은 네트워크(인터넷, 인트라넷)에 일반적이다.

그 중 배열과 연결 리스트에 대해 알아보자.

1. 배열과 연결 리스트

1-1. 배열(Array)

동일한 데이터 타입의 요소들을 순차적으로 저장하는 자료구조이다.

배열은 정적 자료구조로, 미리 크기를 정하고 해당 크기만큼 연속된 메모리 주소를 할당 받는다. 그에 따른 배열의 특징들이 있다.

• 인덱스를 갖는다.
• 대부분 인덱스는 0부터 시작한다.
• 동일한 데이터 타입을 저장한다.
• 고정된 크기를 갖는다.
• 수정은 불가능하다.
• 배열 크기 이상의 데이터는 저장할 수 없다.

내 맘대로 간단히 정리한 배열는 탐색과 접근에 좋은 자료구조이다.

1-2. 연결 리스트(Linked List)

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 선형 자료 구조이다.

연결 리스트는 동적 자료구조로, 미리 크기를 정하지 않아도 된다. 연속 할당하는 배열과 다르게 연속적인 할당이 필요없다. 이에 따른 연결리스트의 특징들이 있다.

• 노드가 존재하며, 노드 안에 데이터와 다음 데이터를 가리키는 링크(주소)가 있다.
• 비연속적인 메모리 할당을 한다.
  연속적 메모리할당이 아니기에 임의로 접근하는 것이 불가능하다.
  즉, 순차적으로 접근해야 한다.
• 삽입 및 삭제가 용이하다.
  요소를 삽입 또는 삭제할 때 해당 위치의 노드의 링크만 변경하면 된다.
• 단일 연결리스트와 이중 연결리스트로 나뉜다.

1. 단일 연결리스트
   : 한 방향 연결, 다음 노드를 알 수 있지만 이전 노드는 알 수 없다. 따라서 역행이 불가하다.

2. 이중 연결리스트
   : 이전, 이후 노드를 모두 저장하고 있어 양방향 이동이 가능하다.

내 맘대로 간단히 정리한 연결리스트는 수정이 자유로운 자료구조이다.

2. 배열과 연결 리스트의 차이점

배열(Array)	연결 리스트(Linked List)
정적 자료구조	동적 자료구조
고정된 크기	유연한 크기
연속된 메모리 주소 할당	비연속된 메모리 주소 할당
접근, 탐색 용이	삽입, 삭제 용이
Index	Node

3. 시간 복잡도

	배열(Array)	연결 리스트(Linked List)
접근	O(1)	O(n)
	→ 인덱스로 직접 접근 가능	→ 직접 접근 불가능
탐색	O(n)	O(n)
	→ 선형 탐색	→ 선형 탐색
삽입, 삭제	O(n)	O(1)
	→ 모든 요소 이동해야해서	→ 삽입, 삭제에 용이

아주 가볍게 개념만 공부해보았는데, 나중에 시간 들여 자세히 공부해야겠다!!

---

참고

• 미트코딩(MeetCoding) 스터디
• 위키백과-배열
• 위키백과-연결 리스트
• TISORY-간략 설명!배열...

아직 공부 중이어서 틀린 내용이나 잘못 이해한 부분이 있을 수 있는데, 그럴 때는 댓글 남겨주세요~!!😊