배열
- 자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉘는데, 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다.
- C 언어를 기준으로 배열은 크기를 지정하고 해당 크기만큼 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말하며, 크기가 고정되어 있어서 한 번 생성한 배열은 크기를 변경하는 것이 불가능하다.
- 배열의 가장 큰 장점은 논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 원하는 요소의 인덱스 값을 알고 있으면 항상 O(1)에 해당 원소에 접근 가능하다는 점
- 예를 들어 int 배열에서 4번째 값에 접근하고 싶다면 (배열의 시작 주소 + (4 - 1) * 4)로 주소를 계산해 한번에 접근 가능하다.
- 단, 삭제 또는 삽입의 경우 원소들의 인덱스를 shift하는 작업이 필요하므로 O(n)의 시간 복잡도를 갖는다.
동적배열
- 동적 배열은 미리 초기값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 차면 늘려주고 모두 복사하는 방식으로 작동한다.
- 동적 배열은 정적 배열과 달리 크기를 지정할 필요가 없어 편리하며, 조회 또한 기존의 배열과 동일하게 O(1)에 가능하다.
- 대부분의 프로그래밍 언어는 동적 배열을 지원하며, 자바에서는 ArrayList, 파이썬에서는 리스트가 동적 배열 자료형이다.
그로스 팩터
- 동적 배열에 할당된 공간이 꽉 차게 되면 보통 더블링이라 하여 2배씩 늘려주게 되는데, 이 재할당 비율을 그로스 팩터라고 한다.
- 파이썬의 그로스 팩터는 초반에는 2배씩 늘려 가지만 전체적으로는 약 1.125배로, 다른 언어에 비해 조금만 늘려가는 형태로 구현되어 있다. (자바의 ArrayList는 1.5배)
- 더블링이 필요한 만큼 공간이 차게 되면, 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업이 필요하므로 O(n)의 비용이 발생하지만, 자주 일어나는 일이 아니므로 분할 상환 분석에 따른 입력 시간은 여전히 O(1)이다.
ArrayList 구현 (JAVA)
import java.util.*;
public class ArrayList<E> implements List<E> {
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ARRAY = {};
Object[] arr = null;
int capacity = 0; // 용량
int size = 0; // 데이터 개수
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException();
}
this.capacity = capacity;
arr = new Object[capacity];
}
public ArrayList() {
this(DEFAULT_CAPACITY);
}
public void resize() {
if (Arrays.equals(arr, EMPTY_ARRAY)) {
arr = new Object[DEFAULT_CAPACITY];
return;
}
if (size >= capacity * 0.75) {
Object[] tmp = new Object[2 * capacity];
System.arraycopy(arr, 0, tmp, 0, size);
arr = tmp;
capacity = 2 * capacity;
}
if (size < (capacity / 2)) {
capacity = capacity / 2;
arr = Arrays.copyOf(arr, Math.max(capacity, DEFAULT_CAPACITY));
}
}
public boolean add(E value) {
if (size == capacity) {
resize();
}
arr[size++] = value;
return true;
}
@Override
public void add(int index, E value) {
if (index >= capacity || index < 0) {
throw new IndexOutOfBoundsException();
}
if (index == size) {
add(value);
}
else {
if (size == capacity) {
resize();
}
if (size - index >= 0) System.arraycopy(arr, index, arr, index + 1, size - index);
arr[index] = value;
size++;
}
}
@SuppressWarnings("unchecked")
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return (E) arr[index];
}
// 데이터 교체
@Override
public E set(int index, E value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
arr[index] = value;
return value;
}
@SuppressWarnings("unchecked")
public E remove(int index) {
Object oldObj = null;
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
oldObj = arr[index];
// 삭제하고자 하는 객체가 마지막 객체가 아닌 경우
if (index != size - 1) {
System.arraycopy(arr, index + 1, arr, index, size - index - 1);
}
// 마지막 데이터를 null로 변경
arr[--size] = null;
return (E) oldObj;
}
public boolean remove(Object value) {
for (int i = 0; i < size; i++) {
if (value.equals(arr[i])) {
remove(i);
return true;
}
}
return false;
}
@Override
public int indexOf(Object value) {
for (int i = 0; i < size; i++) {
if (arr[i].equals(value)) {
return i;
}
}
return -1;
}
@Override
public int lastIndexOf(Object value) {
for (int i = size - 1; i >= 0; i--) {
if (arr[i].equals(value)) {
return i;
}
}
return -1;
}
public Object[] toArray() {
Object[] result = new Object[size];
System.arraycopy(arr, 0, result, 0, size);
return result;
}
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
return (T[]) Arrays.copyOf(arr, size, a.getClass());
}
System.arraycopy(arr, 0, a, 0, size);
return a;
}
@Override
public boolean contains(Object value) {
return indexOf(value) >= 0;
}
public void clear() {
for (int i = 0; i < size; i++) {
arr[i] = null;
}
size = 0;
resize();
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
@Override
public void sort(Comparator c) {
List.super.sort(c);
}
}
연결리스트
- 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로, 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다.
- 배열과 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 O(n)의 시간이 소요된다.
- 하지만 시작 또는 끝 지점에 아이템을 추가하거나 삭제, 추출하는 작업은 O(1)에 가능하다는 장점이 있다.
연결리스트 구현 (JAVA)
public class LinkedList<E> implements List<E> {
static class Node<E> {
E data;
Node<E> prev;
Node<E> next;
Node(E data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node<E> head;
private Node<E> tail;
private int size;
public LinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 특정 위치의 노드를 반환
private Node<E> search(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if (index > size / 2) {
Node<E> x = tail;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
} else {
Node<E> x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
}
public void addFirst(E value) {
Node<E> newNode = new Node<>(value);
newNode.next = head;
// head 노드가 없는 경우에는 NullPointException
if (head != null) {
head.prev = newNode;
}
head = newNode;
size++;
// 요소가 새 노드밖에 없는 경우 새 노드는 head이자 tail
if (head.next == null) {
tail = head;
}
}
@Override
public boolean add(E value) {
if (size == 0) {
addFirst(value);
} else {
addLast(value);
}
return true;
}
public void addLast(E value) {
Node<E> newNode = new Node<>(value);
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
size++;
}
@Override
public void add(int index, E value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
addFirst(value);
return;
}
if (index == size) {
addLast(value);
return;
}
Node<E> prevNode = search(index - 1);
Node<E> nextNode = prevNode.next;
Node<E> newNode = new Node<>(value);
prevNode.next = newNode;
nextNode.prev = newNode;
newNode.prev = prevNode;
newNode.next = nextNode;
size++;
}
public E remove() {
Node<E> headNode = head;
if (headNode == null) {
throw new NoSuchElementException();
}
E result = headNode.data;
Node<E> nextNode = headNode.next;
if (nextNode != null) {
nextNode.prev = null;
}
head = nextNode;
size--;
if (size == 0) {
tail = null;
}
return result;
}
@Override
public E remove(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
return remove();
}
Node<E> prevNode = search(index - 1);
Node<E> node = prevNode.next;
Node<E> nextNode = node.next;
E result = node.data;
prevNode.next = nextNode;
if (nextNode != null) {
nextNode.prev = prevNode;
} else {
tail = prevNode;
}
size--;
return result;
}
@Override
public boolean remove(Object value) {
Node<E> prevNode = head;
Node<E> now = head;
while (now != null) {
if (value.equals(now.data)) {
break;
}
prevNode = now;
now = now.next;
}
if (now == null) {
return false;
}
if (now.equals(head)) {
remove();
}
else {
Node<E> nextNode = now.next;
prevNode.next = nextNode;
if (nextNode != null) {
nextNode.prev = prevNode;
}
else {
tail = prevNode;
}
size--;
}
return true;
}
@Override
public E get(int index) {
return search(index).data;
}
@Override
public E set(int index, E value) {
Node<E> node = search(index);
node.data = value;
return value;
}
@Override
public int indexOf(Object value) {
int index = 0;
Node<E> now = head;
while (now != null) {
if (value.equals(now.data)) {
return index;
}
index++;
now = now.next;
}
return -1;
}
@Override
public int lastIndexOf(Object value) {
int index = size;
Node<E> now = tail;
while (now != null) {
index--;
if (value.equals(now.data)) {
return index;
}
now = now.prev;
}
return -1;
}
@Override
public boolean contains(Object item) {
return indexOf(item) >= 0;
}
// 연결리스트에 있는 요소의 수만큼 배열의 크기가 할당되어 반환
@Override
public Object[] toArray() {
Object[] arr = new Object[size];
int index = 0;
Node<E> node = head;
while (node != null) {
arr[index++] = (E) node.data;
node = node.next;
}
return arr;
}
// 객체 클래스로 상속관계에 있는 타입이거나 데이터 타입을 유연하게 캐스팅 가능
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
}
int index = 0;
// 얕은 복사
Object[] result = a;
Node<E> node = head;
while (node != null) {
// 타입 때문에 a에 바로 값을 할당할 수 없으므로, 얕은 복사 이용
result[index++] = node.data;
node = node.next;
}
return a;
}
@Override
public void clear() {
Node<E> now = head;
while (now != null) {
now = now.next;
}
head = tail = null;
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
}
'Python > Algorithm' 카테고리의 다른 글
트리의 종류와 트리 순회 (0) | 2022.02.26 |
---|---|
최단 경로 알고리즘 (0) | 2022.02.25 |
그래프와 그래프 탐색 (0) | 2022.02.25 |
해시 테이블 (0) | 2022.02.24 |
스택과 큐 (0) | 2022.02.23 |