[자료구조] 02.배열(Array)과 연결리스트(Linked List) 이해하기 개념/비교

---

 

 

 

목차

1. 배열(Array)

2. 연결리스트(Linked List)

3. 시간복잡도

4. 정리

 

 

 

서론

프로그래밍에서 데이터를 효율적으로 저장하고 관리하기 위해 다양한 자료구조가 사용된다. 그 중에서도 배열(Array)과 연결리스트(Linked List)는 가장 기본적이면서도 자주 활용되는 구조이다. 이번 포스팅에서는 배열과 연결리스트에 대해 다뤄보고자 한다.

 

 

배열(Array)

- 같은 자료형의 데이터를 연속된 메모리 공간에 저장하는 정적 자료구조

- index(인덱스)를 이용해 각 요소에 접근 가능 → 임의 접근이 가능하여 접근과 탐색에 용이

- 크기가 고정되어 있어 요소의 삽입이나 삭제가 비효율적 → 수정하는 것이 불가능하고, 해당 배열 크기 이상의 데이터를 저장할 수 없음

 

>  배열의 특징

• index를 이용한 빠른 접근 가능
• 메모리 공간이 연속적으로 할당됨
• 삽입/삭제 시 데이터 이동 발생

>  예시 코드

int[] arr = new int[5]; // 크기가 5인 정수형 배열 생성
arr[0] = 10; // 0 인덱스, 즉 배열의 첫번째 요소에 10을 저장
System.out.println(arr[0]);  // 출력: 10

① 크기가 5인 배열을 생성함
   → arr[0] ~ arr[4] 까지 총 5개의 공간이 생성됨

   ※ 배열은 0부터 시작하는 인덱스 기반이므로 arr[1] 부터 시작하지 않음

② 생성된 배열은 메모리 상에 연속적으로 할당됨
   → arr는 첫 번째 요소의 주소를 참조하게 됨

③ arr[0] = 10; 즉, 배열의 첫 번째 칸에 10이라는 값을 할당함

④ arr[0]을 콘솔에 출력하면 10을 할당했기 때문에 10의 결과가 나옴

 

연결리스트(Linked List)

- 각 요소(Node)가 데이터와 다음 노드에 대한 참조를 가지는 구조 → 연결되어 이어진 형태

- 동적 자료구조로 크기를 정할 필요가 없음- 배열처럼 연속된 메모리 주소를 할당 받지 않음 → 삽입과 삭제가 효율적- 임의 접근이 불가능 → 특정 요소에 접근하려면 앞에서부터 순차적으로 찾아야됨

 

> 연결리스트의 특징

• 동적 메모리 할당 → 유연한 크기 변경 가능
• 삽입/삭제가 빠름
• 접근 속도가 느림

> 예시 코드

LinkedList<Integer> list = new LinkedList<>(); //Integer 타입의 연결리스트 생성
list.add(10); // 리스트에 10 값 추가
list.add(20); // 리스트에 20 값 추가
System.out.println(list.get(0));  // 출력: 10

① Integer 타입의 연결리스트를 생성함
   → Java에서는 객체만 제네릭 타입으로 사용 가능하므로 int가 아닌 Integer 사용

② add() 메소드는 리스트의 끝에 데이터를 추가하는 기능
   → 10 의 정수값을 추가함, 현재 리스트 상태 [10]

③ 같은 방식으로 20 의 정수값을 추가함   → 리스트 상태 [10, 20]

④ list의 첫 번째 요소(0번 인덱스)를 콘솔에 출력하면 결과는 10이 나옴 

 

시간복잡도

- 알고리즘이 입력 크기(n)에 따라 얼마나 빨리 실행되는지를 나타내는 지표

- 최악의 경우를 기준으로 Big-O 표기법( O(n), O(1), O(log n) 등 ) 을 사용

• ※ Big-O 표기법
  • O(1) → 입력 크기와 상관없이 항상 동일한 시간에 동작
  • O(n) → 입력이 많아질수록 실행 시간이 직선적으로 증가

 

> 배열

- 배열은 index를 가지고 있으므로 탐색은 O(1)의 시간복잡도를 가짐

- 삽입의 경우는 맨 뒤라고 한다면 O(1)의 시간복잡도를 가지지만 맨 뒤가 아닌 나머지는 O(n)을 가짐

 

> 연결리스트

- 삽입은 맨 앞일 경우 O(1)의 시간복잡도를, 맨 앞이 아닌 나머지는 O(n)을 가짐

- 탐색은 O(n)의 시간복잡도를 가짐

 

	배열(Array)	연결 리스트(Linked List)
접근	O(1)	O(n)
탐색	O(n)	O(n)
삽입	O(n)	O(1) ~ O(n)
삭제	O(n)	O(1) ~ O(n)

 

---

 

정리

	배열(Array)	연결 리스트(Linked List)
메모리 구조	연속된 메모리	비연속적 메모리(노드끼리 연결)
크기	고정	동적 확장 가능
접근 속도	빠름(O(1))	느림(O(n))
삽입/삭제	느림(데이터 이동 필요)	빠름
사용 용도	빠른 접근이 필요할 때	삽입/삭제가 잦을 때

 

---

 

Reference

https://blacklobster.tistory.com/8

간략 설명! 배열(Array)과 연결 리스트(Linked List)에 대해서 알아보자! - 차이점과 시간복잡도, 활용

https://code-lab1.tistory.com/427

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