리스트와 배열(List and Arrays)

[wongakim-99]

문제 푸는것도 풀고, 조금 더 원론적인 내용을 앞으로 이슈에서 다룬 다음 이와 관련한 문제풀이 예정

• 리스트와 배열 개념 : 차이점과 효율성 비교
• Python에서 리스트 사용법(append, pop, slicing 등)
  (to : 오주 -> 필요하면 자바로 적어도 ㅆㄱㄴ)

---

24/11/27 : 배열과 관련한 기본 개념 [ ✅ ]
24/11/28 : 연결 리스트와 관련한 기본 개념 공부 - 단일 연결 리스트 예시 업로드[ ✅ ]
24/11/29 : 연결 리스트와 관련한 기본 개념 - 이중 연결 리스트에 관한 예시 업로드 및 [ ❌ ]
24/11/30 : 11/29 못한 내용 업로드 [ ✅ ]

[wongakim-99]

1. 리스트와 배열 (List and Arrays)

프로그래밍을 하다 보면 데이터를 효율적으로 관리하고 처리하기 위해 다양한 자료 구조를 사용하게 된다. 자료 구조 중 가장 기본적이며 가장 자주 사용되는 것이 리스트와 배열이다.

리스트와 배열은 모두 데이터의 집합을 저장하기 위한 구조이지만, 내부 구현 방식과 사용법에 있어서 차이가 있다. 왜냐하면 배열은 메모리 상에서 연속적인 공간에 데이터를 저장하는 반면, 리스트는 데이터가 메모리 상의 임의의 위치에 저장될 수 있기 때문이다.

위와 같은 차이점은 리스트와 배열의 성능과 효율성에 영향을 미치며, 각각의 장단점이 존재한다. 따라서 적절한 자료구조를 선택하는 것이 중요하다.

[wongakim-99]

2. 배열 (Array)

• 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
• 데이터가 연속적으로 저장되기 때문에, 특정 인덱스에 빠르게 접근할 수 있다.
• 배열의 크기는 처음 생성할 때 정하며 이후에는 변경이 불가능하다.

이러한 특징 때문에 배열은 대량의 데이터를 다룰 때 메모리 할당에 제약을 받을 수 있다.
예를 들어, 충분한 연속된 메모리 공간이 없다면 큰 크기의 배열을 선언할 수 없다.

위 이미지는 배열의 메모리 구조를 나타낸다. 데이터를 연속적으로 저장하기 때문에 인덱스를 통한 빠른 접근이 가능하다.

---

2-1. 시간 복잡도(Time Complexity)

• 탐색:

  • 특정 인덱스 접근: O(1) (인덱스를 알고 있을 때)
  • 순차적 탐색: O(n) (값을 찾기 위해 모든 데이터를 확인해야 함)

• 삽입/삭제:

  • 처음/중간 삽입 및 삭제: O(n) (삽입/삭제 이후 데이터를 이동해야 함)
  • 끝 삽입 및 삭제: O(1) (데이터 이동 불필요)

---

2-2. 배열의 장단점

장점	단점
특정 인덱스에 O(1)로 접근 가능	크기 고정: 초기 크기를 변경 불가능
메모리 캐시 효율성이 높음	대량의 데이터를 연속 메모리에 할당하기 어려움
구현이 단순하고 코드 작성이 간단	삽입/삭제 시 데이터 이동 필요로 비효율적

---

2-3. 배열을 사용하는 경우

• 순차적인 데이터를 저장하며 값보다는 순서가 중요할 때
• 다차원 데이터를 다룰 때
• 어떤 특정 요소를 빠르게 읽어야 할 때
• 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때

---

추가사항

리스트와 Numpy 배열의 차이

구분	Python 리스트	NumPy 배열
데이터 타입	다양한 타입 허용	단일 데이터 타입 (고정)
성능	상대적으로 느림	빠른 연산 지원
메모리 효율성	비효율적	효율적
고급 연산 지원	기본 연산만 가능	벡터화 연산 및 고급 수학 연산 가능

[wongakim-99]

3. 연결 리스트 (Linked List)

• 연결 리스트는 노드(Node) 라는 데이터 블록이 서로 포인터로 연결된 자료구조이다.
• 배열과 달리 메모리의 연속적인 공간을 필요로 하지 않으며, 동적으로 크기를 조정할 수 있다.
• 각 노드는 두 부분으로 구성된다.
  1. 데이터 (Data) : 실제 저장되는 값
  2. 다음 노드에 대한 참조 (Link) : 다음 노드의 메모리 주소

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next = None

---

3-1. 연결 리스트의 특징

• 메모리의 비연속적인 공간에 데이터를 저장할 수 있다.
• 특정 위치에 빠른 삽입/삭제가 가능하다.
• 특정 요소에 접근하려면 처음부터 순차 탐색을 해야 하므로 랜덤 접근은 느리다.

---

3-2. 연결 리스트의 종류

종류	설명	예시
단일 연결 리스트 (Singly Linked List)	각 노드가 다음 노드만 가리킴. 마지막 노드는 NULL 또는 None으로 끝남.	1 → 2 → 3 → NULL
이중 연결 리스트 (Doubly Linked List)	각 노드가 이전 노드와 다음 노드를 모두 가리킴. 양방향 탐색 가능.	NULL ← 1 ↔ 2 ↔ 3 → NULL
원형 연결 리스트 (Circular Linked List)	마지막 노드가 첫 번째 노드를 가리킴. 리스트가 순환 구조를 가짐.	1 → 2 → 3 → 1

---

3-3. 시간 복잡도

작업	단일 연결 리스트	이중 연결 리스트	설명
탐색	O(n)	O(n)	처음부터 순차적으로 탐색해야 함.
삽입/삭제	O(1) (처음/끝)	O(1) (처음/끝)	노드의 포인터만 변경하면 됨. 중간 삽입/삭제 시 탐색 비용 추가(O(n)).

---

3-4. 연결 리스트의 장단점

장점	단점
동적 크기 조정 가능	특정 요소에 접근하려면 순차 탐색 필요
삽입/삭제가 빠름 (특히 중간 삽입/삭제 시)	추가 메모리 공간(포인터) 필요
메모리의 연속성 요구 없음	구현이 배열보다 복잡

---

3-5. 연결 리스트와 배열의 차이점

특징	배열	연결 리스트
메모리 사용	연속적인 메모리 필요	비연속적인 메모리 사용 가능
크기	고정	동적으로 조정 가능
접근 속도	O(1)	O(n)
삽입/삭제	느림 (O(n), 데이터 이동 필요)	빠름 (O(1), 포인터 변경으로 해결 가능)

---

3-6. 연결 리스트의 사용 사례

• 메모리 효율적으로 데이터를 저장하고 관리할 때
• 크기가 자주 변경되는 데이터
• 삽입 및 삭제가 빈번히 발생하는 경우
• 큐(Queue) 또는 스택(Stack) 구현 시

---

3-7. 연결 리스트 메모리 구조

[wongakim-99]

+배열에 관한 추가 코멘트(array_list.py에 관한 내용)

이전에 내가 배열과 관련한 기본 예제 코드로 업로드 했었다. 그러나 코드를 좀 자세히 보면 배열이 아니...라고는 말을 못하겠으나 조금 더 정확히 설명하면 동적 배열(dynamic array) 처럼 동작한다.

---

왜 배열 관련한 설명에서 List를 사용했는가?

Python 에서는 C나 Java 에서 사용한는 고정 크기의 배열 자료구조가 기본적으로 "없음". 리스트가 그 역할을 대신 수행함
Python에서 리스트는 다양한 기능을 제공하고 동적 크기를 지원, 하지만 배열(Array)은 별도의 모듈(예 : array 혹은 numpy)를 통해 사용할 수 있음. 아래는 Python 리스트와 배열의 차이를 간략히 설명한 표임

특징	Python 리스트	Python 배열 (array 모듈)
데이터 타입	여러 데이터 타입 가능	동일한 데이터 타입만 허용
크기	동적 크기 조정 가능	고정된 크기
성능	데이터 타입 검사로 느림	타입 고정으로 더 빠름
사용 목적	일반적인 용도로 사용	메모리 효율성과 성능 중시
라이브러리 필요 여부	기본 제공	array 또는 numpy 필요

---

Python 리스트는 사실상 배열처럼 동작...

Python 리스트는 내부적으로 동적 배열로 구현되어 있어 배열과 유사하게 사용할 수 있다. 이는 내부적으로 동적 배열(Dynamic Array) 로 구현되어 있으며, 배열과 유사하게 동작한다.

1. 메모리 할당 방식

   • Python 리스트는 요소가 추가될 때마다 새 메모리를 할당하는 대신, 크기 초과를 예상하여 여유 공간을 미리 할당한다.
   • 예를 들어...
     • 초기 리스트의 크기가 4라면, 데이터가 4개까지는 그대로 저장.
     • 다섯 번째 데이터를 추가하면 크기가 8로 증가.

2. 시간 복잡도

   • 데이터 접근 : O(1)
     • Python 리스트는 배열처럼 연속적인 메모리 구조를 사용하기 때문에 특정 인덱스에 즉시 접근할 수 있음.
   • 데이터 추가 :
     • 리스트 끝에 추가할 때 평균적으로 O(1) 이다. 하지만 크기가 초과되면 메모리 재할당이 필요하여 O(n)이 걸릴 수 있다.
   • 데이터 삭제 :
     • 특정 인덱스의 데이터를 삭제하면 나머지 데이터를 이동시켜야 하므로 O(n) 의 시간복잡도가 걸림.

3. 여유 공간 관리

   • Python 리스트는 동적 크기 조정을 위해 capacity 라는 개념을 사용함.
   • len(array)는 현재 요소의 개수를 반환하고, capacity는 리스트가 현재 할당받은 총 메모리 공간을 나타냄.
   • 데이터가 추가되면 :
     • 요소 개수 < capacity : 메모리 확장 없이 데이터를 추가.
     • 요소 개수 > capacity : 새로운 메모리를 할당하고 모든 데이터를 복사.

---

Python 리스트와 배열의 차이

Python 리스트는 배열처럼 동작하지만, 배열보다 더 유연하고 추상화된 기능을 제공한다. 물론 Python 리스트는 배열처럼 동작하지만, 실제로 메모리를 더 많이 사용한다. 대규모 데이터 처리나 고성능 연산이 필요한 경우엔는 numpy 라이브러리의 배열을 사용하는것이 더 효율적이다.

import sys

# 빈 리스트 생성
array = []
print("초기 크기:", sys.getsizeof(array))  # 리스트의 초기 메모리 크기

# 요소를 추가하면서 크기 확인
for i in range(10):
    array.append(i)
    print(f"요소 추가: {i}, 메모리 크기: {sys.getsizeof(array)}")

위의 코드는 실제 동작 확인의 예시이다. Python 리스트의 메모리 확장이 어떻게 이루어지는 직접 확인해보자.

[wongakim-99]

이중 연결 리스트(Doubld Linked List)

Double Linked List	최선	최악
삽입	O(1)	O(1)
삭제	O(1)	O(1)
탐색	O(k)	O(k) [인덱스 탐색 시] O(N) [값 탐색 시]

---

1. 장점

• 싱글 링크드 리스트와 모든 장점을 공유한다.

2. 단점

• Random Access, 배열처럼 index를 통한 탐색이 불가능하다.
• Index를 통해 순차 탐색을 할 경우, 최대 O(N/2) 혹은 O(k)의 시간복잡도가 걸린다.
• Single Linked List 에 비해서 탐색이 최대 2배 정도 더 빠르다. 삽입과 삭제또한 그만큼 빠르다. (그래도 배열보단 느림)
• Value(값)을 통한 순차 탐색을 할 경우, Single Linked List와 마찬가지로 O(N)의 시간복잡도가 걸린다.
• 결론 : 파이썬 리스트 짱짱맨(ㅎ)