Array vs Linked List
Updated:
간단 정리
배열
- 특징
- 논리적 저장순서와 물리적 저장 순서가 일치합니다.
- 인덱스로 해당 원소에 접근이 가능합니다. 그래서 데이터 검색에 유리합니다.
- 인덱스만 알고 있다면 O(1) 가능
- Random Access가 가능합니다.
- 배열의 원소를 삭제할 경우 삭제한 원소보다 큰 인덱스를 가진 원소들을 옮겨줘야(Shift) 하기 때문에 시간 복잡도 O(n)이 걸립니다.
- 삽입의 경우, 새로운 원소를 추가하고 모든 원소들의 인덱스를 1씩 Shift 해줘야 하므로 시간 복잡도 O(n)이 걸립니다.
- 제한적인 크기를 갖습니다.
링크드리스트
-
특징
- 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조를 갖습니다.
- 배열과 다르게 element와 element 간의 연결(link)을 이용해서 리스트를 구현한 것입니다.
- 트리의 근간이 되는 자료구조입니다.
-
장점
- 삽입과 삭제가 O(1)에 이루어집니다.
- 삽입과 삭제를 할 때마다 동적으로 링크드 리스트의 크기가 결정되므로 전통적인 배열(Array)에 비해 처음부터 큰 공간을 할당할 필요가 없어집니다.
- 메모리 관리가 용이합니다. (사실상 이게 가장 큰 이유.)
- 삽입과 삭제가 O(1)에 이루어집니다.
-
단점
- Random Access, 즉 배열처럼 index를 통해 탐색이 불가능합니다.
- 탐색이 O(N)이 걸립니다. (Head부터 Tail까지 모두 탐색 시)
- 삽입과 삭제
- 사실상 삽입과 삭제가 왼쪽에서(Head에서) 이루어지지 않을 경우, 결국 탐색을 먼저 해야 하기 때문에 삽입과 삭제 모두 적게는 O(k)부터 최악의 경우 O(N)까지 걸릴 가능성이 있습니다.
- 파이썬에서 링크드 리스트는 의미가 크게 없는 게, 그냥 리스트 쓰면 된다. C++의 STL vector보다도 훨씬 쓰기 간편하며, 어떠한 타입의 데이터도(심지어 튜플이나 리스트마저) 넣을 수 있고 동적으로 메모리 관리가 되기 때문에, 링크드 리스트의 의미가 크게 퇴색됩니다.
-
linked list 코드
-
# Node 클래스 정의 class Node: def __init__(self, data): self.data = data self.next = None # LinkedList 클래스 (자료구조) 정의 class LinkedList: # 초기화 메소드 def __init__(self): dummy = Node("dummy") self.head = dummy self.tail = dummy self.current = None self.before = None self.num_of_data = 0 # append 메소드 (insert - 맨 뒤에 노드 추가, tail과 node의 next, 데이터 개수 변경) def append(self, data): new_node = Node(data) self.tail.next = new_node self.tail = new_node self.num_of_data += 1 # delete 메소드 (delete - current 노드 삭제, 인접 노드의 current, next 변경, 데이터 개수 변경) def delete(self): pop_data = self.current.data if self.current is self.tail: self.tail = self.before self.before.next = self.current.next self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다. # self.num_of_data -= 1 return pop_data # first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경) def first(self): if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴 return None self.before = self.head self.current = self.head.next return self.current.data # next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함) def next(self): if self.current.next == None: return None self.before = self.current self.current = self.current.next return self.current.data def size(self): return self.num_of_data
-
차이
연산시간
- 데이터 접근 속도
- Array > Linked List
- Array
- 인덱스를 사용해 빠르게 원소에 접근할 수 있습니다. 따라서 Random Access를 지원합니다.
시간 복잡도 O(1)
로 빠르게 찾을 수 있습니다.
- Linked List
- Sequential Access (순차 접근 방식)을 사용합니다.
- 특정 원소에 접근하기 위해서는 처음부터 원소에 도달할 때까지 순차적으로 검색하면서 찾습니다.
시간 복잡도 O(N)
- 데이터 삽입 속도
- 보통 Linked List > Array
- Array
- 데이터를 중간이나 맨 앞에 삽입할 경우, 그 이후의 데이터를 한 칸씩 미뤄야 하는 추가 과정과 시간이 소요됩니다.
- 데이터가 많을 경우 비효율적입니다.
- 그렇기 때문에 LinkedList가 필요하게 되었습니다.
- Linked List
- 어느 곳에 삽입하던지 O(n)의 시간복잡도를 갖습니다.
- 삽입할 위치를 찾고(O(n)) 삽입 연산을 진행하기 때문에 O(N)의 시간 복잡도를 갖습니다.
- 만약, 중간 삽입이 없다면 즉 맨 앞과 맨 뒤에만 삽입한다면
시간 복잡도 : O(1)
- 어느 곳에 삽입하던지 O(n)의 시간복잡도를 갖습니다.
- 데이터 삭제 속도
- 이 부분도 경우에 따라 다릅니다. (보통 Linked List > Array)
- Array
- 그 위치의 데이터를 삭제 후, 전체적으로 Shift 해줘야 합니다.
시간 복잡도 O(N)
- LinkedList
- 삭제할 원소를 찾기 위해서 O(N)의 시간 복잡도를 갖고 삭제를 합니다.
시간 복잡도 O(N)
- 하지만 Array 보다 빠르게 삭제 연산을 수행합니다.
- 만약, 중간 삭제가 없고 맨 앞과 뒤에서만 삭제한다면
시간 복잡 O(1)
저장 방식
- Array
- element들은 인접한 memory 위치에 저장 되거나 memory에 연이어 저장됩니다.
- LinkedList
- 새로운 element들은 memory 어딘가에 저장되어 되어집니다.
- 새로운 element에 할당된 memory 위치 주소는 linked list의 이전 node에 저장되어집니다.
Memory Allocation (메모리 할당)
- Array
- Array가 선언되자 마자 memory는 compile time에 할당되어집니다.
- 이것을 Static Memory Allocation (정적 메모리 할당)이라고 불립니다.
- Array는 Stack 영역에 memory 할당이 이루어집니다.
- LinkedList
- 메모리는 새로운 node가 추가될 때 runtime에 할당되어집니다.
- 이것을 Dynamic Memory Allocation (동적 메모리 할당)이라고 불립니다.
- LinkedList는 Heap 영역에 memory 할당이 이루어집니다.
- static memory allocation vs dynamic memory allocation
- static memory allocation
- 고정된 영역에만 memory를 할당합니다.
- dynamic memory allocation
- 프로세스가 돌아가는 runtime 내에 영역의 크기를 알려줌으로써 영역을 확보합니다.
- static memory allocation
- Stack vs Heap
- stack
- 메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역입니다.
- 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸합니다.
- 이렇게 스택 영역에 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 합니다.
- 스택 영역은 푸시(push) 동작으로 데이터를 저장하고, 팝(pop) 동작으로 데이터를 인출합니다.
- 이러한 스택은 후입선출(LIFO, Last-In First-Out) 방식에 따라 동작하므로, 가장 늦게 저장된 데이터가 가장 먼저 인출됩니다.
- 스택 영역은 메모리의 높은 주소에서 낮은 주소의 방향으로 할당됩니다.
- heap
- 변수는 전역적으로 접근이 가능합니다.
- 메모리의 힙(heap) 영역은 사용자가 직접 관리할 수 있는 ‘그리고 해야만 하는’ 메모리 영역입니다.
- 힙 영역은 사용자에 의해 메모리 공간이 동적으로 할당되고 해제됩니다.
- 힙 영역은 메모리의 낮은 주소에서 높은 주소의 방향으로 할당됩니다.
- stack
Size
- array
- size는 반드시 array 선언 시점에 지정되어있어야 합니다.
- LinkedList
- size는 다양할 수 있습니다.
- node들이 추가될 때 runtime 시점에서 LinkedList size는 커질 수 있기 때문입니다.
종류
- Array
- single dimensional
- two dimensional
- multidimensional
- Linked List
- Linear(Singly) linked list
- Doubly linked list
- Circular linked list
번외 1) 배열(Array)과 리스트(ArrayList)의 차이는?
- 정리
- 배열
- 데이터의 크기가 정해져 있고,
- 추가적인 삽입 삭제가 일어 나지 않으며,
- 검색을 필요로 할 때 유리합니다.
- 리스트
- 데이터의 크기가 정해져 있지 않고,
- 데이터에 순서가 있으며,
- 삽입 삭제가 많이 일어나고,
- 검색이 적은 경우 유리합니다.
- 배열
- 배열
- 특징
- 같은 자료형을 가진 변수를 하나로 나타낸 것입니다.
- 연속된 메모리 공간으로 이루어져있는 것입니다.
- 정적으로 표현됩니다.
- 인덱스를 이용하여 표현합니다.
- 지역성을 가지고 있습니다다.
- 장단점
- 배열의 장점
- 인덱스를 통한 검색이 용이합니다.
- 연속적이므로 메모리 관리가 편합니다.
- 배열의 단점
- 한 데이터를 삭제하더라도 배열은 연속해야 하므로 공간이 남습니다.
- 즉, 메모리가 낭비됩니다.
- 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 합니다.
- 컴파일 이후 배열의 크기를 변동 할 수 없습니다.
- 한 데이터를 삭제하더라도 배열은 연속해야 하므로 공간이 남습니다.
- 배열의 장점
- 제공언어
- Java
- Javascript (자바스크립트는 배열에 리스트 기능 포함)
- C
- 특징
- 리스트
- 특징
- 순서가 있는 데이터의 집합입니다.
- 불연속적으로 메모리 공간을 차지합니다.
- 동적으로 표현됩니다,
- 인덱스가 없습니다.
- 포인터를 통해 접근합니다.
- 리스트의 장단점
- 리스트의 장점
- 포인터를 통하여 다음 데이터의 위치를 가르키고 있어 삽입 삭제가 용이합니다.
- 동적이므로 크기가 정해져 있지 않습니다.
- 메모리의 재사용 편리합니다.
- 불연속적이므로 메모리 관리가 편리합니다.
- 리스트의 단점
- 검색 성능이 좋지 않습니다.
- 포인터를 통해 다음 데이터를 가르키므로 추가적인 메모리 공간이 발생합니다.
- 리스트의 장점
- 제공언어
- Python
- Java
- 특징
번외 2) Doubly Linked List
-
시간복잡도
-
장점
- 싱글 링크드 리스트와 모든 장점을 공유합니다.
- 삽입과 삭제가 O(1)에 이루어집니다.
- 삽입과 삭제를 할 때마다 동적으로 링크드 리스트의 크기가 결정되므로 전통적인 배열(Array)에 비해 처음부터 큰 공간을 할당할 필요가 없어집니다.
- 메모리 관리가 용이합니다. (사실상 이게 가장 큰 이유입니다.)
- 싱글 링크드 리스트와 모든 장점을 공유합니다.
-
단점
-
Random Access, 즉 배열처럼 index를 통해 탐색이 불가능합니다.
-
Index를 통해 순차 탐색을 할 경우, 최대 O(N/2) 혹은 O(k)의 시간복잡도가 걸립니다.
-
아래 소스 코드를 보면 더블 링크드 리스트의 크기와 탐색하고자 하는 index의 크기를 비교하여 head와 tail 중 더 가까운 곳에서 탐색을 시작합니다.
-
그러므로 싱글 링크드 리스트에 비해 가지는 장점은 탐색이 최대 2배 더 빠르므로, 삽입과 삭제 또한 그만큼 빠릅니다.
그래도 배열보다 느립니다.
-
-
Value(값)를 통해 순차 탐색을 할 경우, 싱글 링크드 리스트와 마찬가지로 O(N)의 시간복잡도가 걸립니다. (단, 현재 소스 코드에서는 Value를 통한 탐색은 구현하지 않았습니다.)
-
-
Doubly Linked List 코드
#Double Linked List class Node(object): def __init__(self, data, prev = None, next = None): self.data = data self.prev = prev self.next = next class DList(object): def __init__(self): self.head = Node(None) self.tail = Node(None, self.head) self.head.next = self.tail self.size = 0 def listSize(self): return self.size def is_empty(self): if self.size != 0: return False else: return True def selectNode(self, idx): if idx > self.size: print("Overflow: Index Error") return None if idx == 0: return self.head if idx == self.size: return self.tail if idx >= self.size//2: target = self.head for _ in range(idx): target = target.next return target else: target = self.tail for _ in range(self.size - idx): target = target.prev return target def appendleft(self, value): if self.is_empty(): self.head = Node(value) self.tail = Node(None, self.head) self.head.next = self.tail else: tmp = self.head self.head = Node(value, None, self.head) tmp.prev = self.head self.size += 1 def append(self, value): if self.is_empty(): self.head = Node(value) self.tail = Node(None, self.head) self.head.next = self.tail else: tmp = self.tail.prev newNode = Node(value, tmp, self.tail) tmp.next = newNode self.tail.prev = newNode self.size += 1 def insert(self, value, idx): if self.is_empty(): self.head = Node(value) self.tail = Node(None, self.head) self.head.next = self.tail else: tmp = self.selectNode(idx) if tmp == None: return if tmp == self.head: self.appendleft(value) elif tmp == self.tail: self.append(value) else: tmp_prev = tmp.prev newNode = Node(value, tmp_prev, tmp) tmp_prev.next = newNode tmp.prev = newNode self.size += 1 def delete(self, idx): if self.is_empty(): print("Underflow Error") return else: tmp = self.selectNode(idx) if tmp == None: return elif tmp == self.head: tmp = self.head self.head = self.head.next elif tmp == self.tail: tmp = self.tail self.tail = self.tail.prev else: tmp.prev.next = tmp.next tmp.next.prev = tmp.prev del(tmp) self.size -= 1 def printlist(self): target = self.head while target != self.tail: if target.next != self.tail: print(target.data, '<=> ', end='') else: print(target.data) target = target.next
Leave a comment