3. 배열(Array)
배열은 자료구조의 하나로, 동일한 데이터 타입의 요소들을 순차적으로 저장하는 컨테이너이다.
배열은 메모리에서 연속적으로 할당된 공간에 요소들을 저장하므로, 특정 인덱스를 기반으로 한 접근이 가능하다.
특징:
인덱스: 배열의 각 요소는 0부터 시작하는 인덱스를 가진다.
예를 들어, 첫 번째 요소는 인덱스 0에 저장되고, 두 번째 요소는 인덱스 1에 저장된다.
크기: 배열의 크기는 배열에 저장할 수 있는 요소의 개수를 나타냅니다. 크기는 배열을 생성할 때 결정되며,
이후에 변경할 수 없다.
연속적인 메모리 할당: 배열은 메모리에서 연속적으로 할당된 공간에 요소를 저장한다.
이는 인덱스를 통한 빠른 접근과 메모리 캐시 효율성을 제공한다.
동일한 데이터 타입: 배열은 동일한 데이터 타입의 요소들로 구성되어야 한다.
예를 들어, 정수형 배열은 정수 값들만 저장할 수 있다.
데이터의 순차적인 저장이 필요한 경우, 배열은 효율적인 선택이다.
배열을 사용하면 인덱스를 통해 원하는 요소를 직접 접근하고 수정할 수 있으며,
반복문을 사용하여 배열의 모든 요소에 접근하는 것도 간단하다.
같은 형태의 자료를 효율적으로 관리하기 위해 사용하기에도 적합하다.
하지만 배열의 크기가 고정되어 있기 때문에(= '정해진 공간'에 한정),
요소를 삽입하거나 삭제하는 작업에는 제한이 있다. 요소의 삽입 또는 삭제가 빈번하게 일어나는 경우,
동적 배열이나 연결 리스트와 같은 다른 자료구조를 고려해야 한다.
# 배열을 사용하는 예시
# 내장라이브러리의 array 모듈 import
import array
# 정수를 취급하는 배열 ar1이라는 변수 생성
ar1 = array.array('i', [1,2,3,4]) # i: int (f: float, u:string)
print(type(ar1))
for i in ar1:
print(i, type(i))
# array 안에 int가 있다는 것을 알 수 있음.
# 문자열을 취급하는 배열 ar2라는 변수 생성
ar2 = array.array('u', ['가', 'I', '1'])
for e in ar2:
print(e, type(e))
# 외부라이브러리 numpy 모듈 import
import numpy as np
ay1 = np.array([1,2,3,4], dtype=np.int64)
print(ay1)
for i in ay1:
print(i, type(i))
# array모듈과의 차이점: 1을 1.0으로 type이 다르게 입력되어도 자동으로 변경이 되어 오류가 발생하지 않음.
ay2 = np.array([1,2,3,4], dtype=np.float32)
print(ay2)
for i in ay2:
print(i, type(i))
ay3 = np.array([1,2,3,'4'], dtype=np.str_)
print(ay3)
for i in ay3:
print(i, type(i))
# array모듈과의 차이점: 4을 '4'로 type이 다르게 입력되어도 자동으로 변경이 되어 오류가 발생하지 않음.
4. 리스트(List)
리스트는 자료구조의 일종으로, 서로 다른 데이터 타입의 요소들을 순서대로 저장하는 동적 컨테이너이다.
각 요소는 인덱스를 사용하여 접근할 수 있습니다. 리스트는 배열과는 달리 크기가 동적으로 조정될 수 있어 삽입, 삭제, 수정 등의 연산이 유연하게 이루어질 수 있다.
특징:
동적 크기: 리스트는 동적으로 크기를 조정할 수 있다.
요소의 삽입 또는 삭제가 발생할 때마다 크기가 자동으로 조정되어 메모리의 효율적인 사용이 가능하다.
다양한 데이터 타입: 리스트는 서로 다른 데이터 타입의 요소를 저장할 수 있다.
예를 들어, 정수, 문자열, 객체 등을 한 리스트에 저장할 수 있다.
연결 구조: 리스트는 각 요소가 연결되어 있는 구조를 가지고 있다.
각 요소는 값과 다음 요소를 가리키는 포인터로 구성되어 있어 순차적인 접근이 가능하다.
삽입과 삭제: 리스트는 요소의 삽입과 삭제가 상대적으로 간단하고 효율적이다.
요소를 삽입할 때는 해당 위치에 새로운 요소를 추가하고, 요소를 삭제할 때는 해당 위치의 요소를 제거하여 연결 구조를 업데이트한다.
리스트는 다양한 용도로 사용된다. 데이터의 동적인 관리가 필요한 경우, 리스트는 유용한 선택이다.
요소의 삽입, 삭제, 탐색 등의 작업이 빈번하게 발생하는 경우 리스트는 배열보다 효율적이다.
또한, 리스트는 스택, 큐, 연결 리스트 등의 자료구조를 구현하는 데에도 사용될 수 있다.
리스트는 대부분의 프로그래밍 언어에서 내장된 자료구조로 제공되며,
리스트를 활용하는 다양한 연산들도 제공된다.
예를 들어, 요소의 추가, 삭제, 검색, 정렬, 반전 등의 연산을 수행할 수 있다.
* 구현 방법:
1. 그대로 배열을 이용해서 리스트 생성. 연속배열. ArrayList(JAVA용어)
2. 자료들의 연결확인만으로도 충분. 연결구조. LinkedList(JAVA용어)
* 언어별 지원 (언어별로 지원하는 내용이 조금씩 다르다)
- C: 배열 O, 리스트 X
- JAVA: 배열 O, 리스트 O
- Python: 배열 X, 리스트 O (ArrayList를 통해 리스트를 구현함)
- JavaScript: 단점을 개선한 배열 O, 리스트 O
4-1. ArrayList
ArrayList는 배열 기반의 리스트 자료구조를 구현하는 방식으로, 내부적으로 배열을 사용하여 요소를 저장함.
요소의 삽입, 삭제, 접근 등의 작업이 빠르게 이루어짐.
배열의 인덱스를 사용하여 요소에 접근할 수 있으므로 임의 접근이 용이함.
요소를 삽입하거나 삭제할 때, 해당 위치의 요소들을 이동시켜야 하므로 성능 저하가 발생할 수 있음.
크기를 동적으로 조정할 수 있으며, 배열의 크기가 부족할 경우 자동으로 더 큰 배열을 할당하여 요소를 복사.
순차적인 접근이 많고 요소의 삽입, 삭제가 상대적으로 적은 경우에 적합함.
4-2. LinkedList
LinkedList는 연결 기반의 리스트 자료구조를 구현하는 방식으로,
각 요소가 다음 요소를 가리키는 포인터로 연결되어 있음.
삽입 또는 삭제 시, 단순히 포인터를 조정하는 작업만 수행하면 되므로 요소의 삽입, 삭제가 빠르게 이루어짐. 요소에 접근하기 위해서는 처음부터 순차적으로 찾아가야 하므로 임의 접근에는 비효율적임.
크기를 동적으로 조정할 수 있으며, 삽입 또는 삭제 시에는 새로운 요소를 생성하여 연결 구조에 맞게 연결함.
저장공간의 압박이 없으며, 순차적인 접근과 요소의 삽입, 삭제가 빈번한 경우에 적합함.
LinkedList는 노드들로 구성된 연결 리스트.
inkedList는 첫 번째 노드를 가리키는 헤드(Head) 포인터를 가지고 있음.
첫 번째 노드를 가리키는 헤드 포인터를 통해 LinkedList의 시작점을 알 수 있음.
각 노드는 다음 노드를 가리키는 링크 필드를 통해 다음 노드와 연결됨.
마지막 노드는 다음 노드를 가리키는 링크 필드가 null로 설정되어 연결의 끝을 나타냄.
노드와 노드 간의 연결 관계를 통해 LinkedList는 순차적인 데이터의 저장과 순회를 가능하게 함.
노드 간의 링크를 따라가면서 순차적으로 데이터에 접근할 수 있기 때문에 첫번째 노드의 위치만
기억하면 됨.
새로운 노드를 삽입하거나 기존의 노드를 삭제할 때는 링크 필드를 조정하여 연결 관계를 변경함.
# Node 클래스를 정의하고, 두 개의 노드 객체를 생성하여 출력하는 예시
class Node:
# Node 클래스의 생성자로 객체가 생성될 때 호출되며, new_item과 next_node라는 두 개의 매개변수를 받음
def __init__(self, new_item, next_node):
self.item = new_item
self.next = next_node
# n1은 'first'라는 데이터를 가지고 있으며, next 속성은 None으로 설정되어 다음 노드를 가리키지 않음.
# n2는 'second'라는 데이터를 가지고 있으며, next 속성도 None으로 설정되어 다음 노드를 가리키지 않음.
n1 = Node('first', None)
n2 = Node('second', None)
# 첫 번째 print 문에서 n1을 출력하면, 해당 노드 객체의 주소값과 클래스의 타입인 Node가 출력됨.
# 두 번째 print 문에서 n1.item과 n1.next를 출력하면, n1 노드 객체의 item 속성과 next 속성의 값이 출력됨.
# 세 번째 print 문은 n2와 해당 클래스의 타입인 Node가 출력됨.
print(n1, type(n1))
print(n1.item, n1.next)
print(n2, type(n2))
n1과 n2의 연결
# n1.next = n2는 n1 노드의 next 속성에 n2 노드를 할당함. 이로써 n1 다음에 n2가 위치하게 됨.
n1.next = n2 # 연결
# print(n1.next)는 n1 노드의 next 속성을 출력함. 이때 출력되는 값은 n2의 주소값임.
print(n1.next) # n1.next 위치가 n2의 주소값이 그대로 나옴.
# print(n1.next.item, n2.item)은 n1 노드의 next 속성인 n2의 item 속성과 n2의 item 속성을 출력함.
# 즉, n1 다음에 위치한 n2의 데이터 값을 출력함.
print(n1.next.item, n2.item) # n1.next.item과 n2.item이 동일하다 = 정상적 연결
4-2-1. 기능
필수요소:
head: LinkedList에서 첫 번째 노드의 위치를 기억하는 속성. 이를 통해 LinkedList의 시작점을 알 수 있음.
num_items: LinkedList에 저장된 원소의 총 개수를 나타내는 속성.
메서드(쿼리):
.append(x): LinkedList의 맨 뒤에 새로운 원소 x를 추가.
.insert(i, x): 특정 위치 i에 새로운 원소 x를 추가.
.remove(x): LinkedList에서 첫 번째로 나타나는 원소 x를 삭제.
.pop(i): 특정 위치 i에 있는 원소를 삭제.
- .get(i): i번째 데이터 조회.
- .index(x): 원소 x가 몇번째 index인지 확인.
- .is_empty(): 빈 리스트인지 확인
- .size(): 총 데이터 수의 확인
-. clear : 모든 데이터 삭제
삽입
* .append(x)
# append의 의사코드
* .insert(i, x) # i가 0이 아닐 경우
* .insert(i = 0, x) # i가 0일 경우
n1의 next 값은 기존에 있던 head의 값을 연결함.
* 삽입 기능 개선안
더미 헤드(dummy head) LinkedList에서 사용되는 특별한 종류의 노드이다. 더미 헤드는 실제 데이터를 저장하지 않고, 단지 LinkedList의 시작점을 나타내는 역할을 수행한다. 일반적인 LinkedList에서는 첫 번째 노드가 실제 데이터를 저장하는 역할과 함께 시작점 역할을 수행한다. 그러나 때로는 첫 번째 노드를 따로 처리하는 로직을 작성해야 할 때가 있다. 이를 위해 더미 헤드를 사용할 수 있다. 실제 데이터를 저장하는 첫 번째 노드와는 별도로 더미 헤드라는 노드를 추가로 사용하여 LinkedList를 시작할 수 있다. 더미 헤드는 데이터를 저장하지 않기 때문에 실제 데이터를 저장하는 첫 번째 노드와 구분할 수 있다. 더미 헤드의 이점: 코드의 단순화: 더미 헤드를 사용하면 첫 번째 노드를 따로 처리하는 로직을 구현할 필요가 없어진다. 예외 처리 간소화: 더미 헤드를 사용하면 빈 LinkedList에 대한 예외 처리를 따로 구현할 필요가 없다. |
# 더미노드 존재 시
삭제
* .remove(x)
* .pop(i)
1) 더미헤드를 사용하지 않을 경우, 중간에서 끝을 삭제.
2) 더미헤드를 사용하지 않을 경우, 첫번째 노드 삭제.
3) 더미헤드 사용 시
