배열
배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다. 배열에 포함된 원소는 순서대로 index가 붙는다.
(정적) 배열의 특징
-
기본적으로 배열은 고정된 크기를 가지며, 동적으로 크기를 늘릴 수 없다.
예를 들어 배열의 크기를 3 → 4로 늘리고 싶다면 새 메모리를 할당하고 기존 배열의 값을 하나씩 옮겨주어야 한다.c의 경우가 이렇다. 하지만javascript,python에서는 배열의 크기가 자동으로 조절된다.일반적으로 '배열'이라고 하면 정적 배열을 의미한다.
-
원하는 원소의 index를 알고 있으면 O(1)로 원소를 찾을 수 있다.
→ 배열은 탐색에 유리한 구조
하지만 정렬되지 않은 배열에서 특정 값을 탐색하는 경우, 요소의 처음부터 값을 발견할 때까지 선형 탐색해야 한다. → O(n) -
원소를 삭제하면 index가 당겨지지 않고 해당 index에 빈자리가 생긴다. 따라서 원소를 삭제 or 추가하려면 최대 O(n)이 소요된다.
→ 추가와 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다.
자바스크립트에서 배열
- 자바스크립트의 배열은 지금까지 살펴본 일반적 의미의 배열과는 다르다. 배열의 요소를 위한 각 메모리 공간은 동일한 크기를 가지지 않아도 되며 연속적으로 이어져 있지 않아도 된다. 배열에 속한 요소의 위치가 연속적이지 않은 배열을 희소배열이라고 한다.
→ 배열 요소의 index가 연속적이지 않아도 되며, 따라서 특정 배열 요소가 비어있을 수 있다.
var arr = new array() // 빈 배열 객체 생성
arr[99] = "javascript" // 배열 arr의 100번째 위치에 문자열 삽입
arr.length // 배열의 길이는 100 - 자바스크립트의 배열은 해시태이블로 구현된 객체이다. 따라서 index로 숫자 대신 문자열로 된 key를 사용할 수 있는데 이러한 배열을 연관배열이라고 한다. 하지만 이렇게 생성된 배열은 자바스크립트 내부적으로
Array 객체에서기본 객체로 재선언된다. 따라서 기존Array 객체에서 사용할 수 있는 메소드와 속성이 정확하지 않은 결과값을 반환하게 된다.
var arr = new array() // 빈 배열 객체 생성
arr['하나'] = 1
arr["참"] = true
arr["자바스크립트'] = 'javascript'
console.log(arr["참"]) // 문자열을 인덱스로 배열 요소에 접근
console.log(arr.length) // 연과배열은 Array 객체가 아니므로 길이가 0
console.log(arr[0]) //undefined 자바스크립트의 배열은 해시태이블로 구현된 객체이므로 인덱스로 배열에 접근하는 경우 일반적인 배열보다 느리지만, 특정 요소를 탐색하거나 요소를 추가 or 삭제하는 경우에는 일반적인 배열보다 빠르다.
연결리스트
연결리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.
배열은 메모리를 연속적으로 사용하지만, 연결리스트는 퍼져있는 메모리 영역을 알기 위해 포인터를 사용해 각 영역을 참조한다.
연결리스트 특징
- 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
- 요소 탐색 : O(n)
- 요소 추가 or 제거 : O(1)
- 종류 : singly linked list, doubly linked list, circular linked list
1)singly linked list: head에서 tail까지 단방향으로 이어짐
2)doubly linked list: 양방향을 이어지는 연결리스트, singly linked list보다 자료구조의 크기가 조금 더 크다.
3)circular linked list: singly or doubly linked list에서 tail이 head로 연결되는 연결리스트
자바스크립트에서 연결리스트
// Data와 다음을 가리키는 포인터 Next를 가지고 있는 Node 객체
class Node{
constructor(value){
this.value = value
this.next = null // linked list의 tail은 null로 끝나기때문
}
}
class SinglyLinkedList{
constructor(){
this.head = null // 처음에 데이터가 없다면 null이다.
this.tail = null // 첫 번째 노드와 마지막 노드를 가리키는 head,tail
}
append(newvalue){
var newNode = new Node(newvalue)
if(this.head === null){
this.head = newNode
this.tail = newNode
}
else {
this.tail.next = newNode
this.tail = newNode
}
}
find(value){
var curnode = this.head
while (curnode.value !== value){
curnode = curnode.next
}
return curnode
}
insert(newvalue, value){
var newNode = new Node(newvalue)
newNode.next = this.find(value).next
this.find(value).next = newNode
}
findPrevious(value) {
var currNode = this.head;
while(currNode.next != null && currNode.next.value != value) {
currNode = currNode.next;
}
return currNode;
}
remove(item) {
var preNode = this.findPrevious(item);
preNode.next = preNode.next.next;
}
// remove 메소드는 완벽하지 않음, prenode가 head일때 오류
display(){
var str = '[ ';
var curnode = this.head
while(curnode.next !== null){
str += curnode.value+' ';
curnode = curnode.next;
}
return str + curnode.value + ']';
}
}