코딩테스트를 이전에 보았었는데 큰 어려움을 느꼈었다. 원인으로 자료구조에 대한 이해가 부족함을 깨닫고 유데미에서 알고리즘 강의를 두 가지 듣게 되었다. 시간 복잡도와 공간 복잡도.. 등에 대한 개념과 여러 자료구조를 접하고 보고 퀴즈를 풀 수는 있었지만 그것을 직접 코드로 만들어내는 부분, 실제로 알고리즘 문제를 풀어낼 때 연결할 수 있는 부분이 약했다. 강의를 통해 스스로 시각화를 해내는 법을 익혔지만 휘발성이 강하여 강제로 계속 반복적으로 기억해 내기 위해 Linked list라는 주제부터 꺼내오게 되었다. 그리고 어째서 이 자료구조에 대한 특성들을 알아야 하는가,,에 대한 고찰을 담아보려 한다.
시간복잡도 Big O에 대한 개념 설명은 생략한다!
Linked List 연결 리스트
요소 간의 연결(Link)을 이용하여 리스트를 구현한 선형 자료구조.
Linked List의 엘리먼트들은 특정 메모리 주소나 인덱스에 저장되지 않는다.
구성요소
Head
Linked list의 가장 첫 번째 지점, 첫 번째 노드!
Node
Linked List의 기본 단위로, 저장할 데이터value와 다음 노드 next node를 가리키는 포인터로 구성되어 있다. next node의 값은 null로 초기화된다.
Tail
Linked list의 마지막 노드. 이 이후에는 노드가 없으므로 마지막 노드는 항상 null을 가리킨다(Circular Linked List 제외). null은 어떠한 위치도 가리키지 않는다.
▶︎ 노드들이 메모리상에 임의의 위치에 생성되더라도 사실 물리적인 위치가 어디인가는 전혀 중요하지 않으며 그것과 상관없이 Link에 의해 서로 논리적으로 연결되어 있으므로 일직선으로 그리는 것이 보통이다.
위 Linked List의 구조를 JavaScript로 아래처럼 표현할 수 있다
const list = {
head: {
value: 11
next: {
value: 18
next: {
value: 24
next: null
}
}
}
}
};Array List와의 차이점?
▶︎ Array와 헷갈릴 수 있는데, Array List는 Index인덱스로 엘리먼트에 접근하는 방식을 취하지만 Linked List는 다음 엘리턴트를 가리키는 Pointer포인터를 사용하여 각 엘리먼트의 순서를 구현한다. 엘리먼트가 메모리의 도처에 흩어져서 존재하지만 Link에 의해 논리적으로 연결되어 있기 때문에 이전, 이후 요소를 찾을 수 있다.
✔️ 이를 통해 일어나는 장단점
Array의 경우 중간에 삽입을 위해선 밀림(Shift)가 일어나고 인덱스도 업데이트되지만, Linked List의 경우 얼마든지 동적으로 새로운 노드가 추가될 수 있고, 포인터 방식으로 인해 밀림이 없다. 다만 삽입, 제거 등을 위해 노드를 찾아가는 작업이 Array에 비해 오래 걸린다. Array의 경우 인덱스를 통해 직접 접근이 가능하지만 Linked List는 포인터를 따라 리스트를 순회해야 한다.
Linked List의 유형
- Link를 하나만 가진 Single Linked List단순 연결 리스트
- 두 개의 Link를 가진 Double Linked List이중 연결 리스트
- 마지막 Node가 최초의 노드를 참조하는 Circular Linked List원형 연결 리스트
JavaScript로 Node와 Single Linked List 코드로 구현해보기
// Linked List의 Node
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
// Linked List 전체
class LinkedList {
constructor(value) {
const newNode = new Node(value);
this.head = newNode;
this.tail = this.head;
this.length = 1; // 필수값 아님!
}
}
Node와 그에 대한 모음인 Linked List에 대해 초기화를 해준다. 이제 값을 가진 노드들이 모인 Linked List를 만들어보자!
push
✔️ 고려해보아야 할 점
Node의 존재 유무? 없을 경우엔 어떻게 할 것이고, 있을 경우엔 어떻게 해주면 될까?
// push - 마지막 요소에 추가 | value를 받아와서 그 값을 가진 새로운 노드를 생성하려 한다.
push(value) {
const newNode = new Node(value);
// 현재 리스트가 비어있는지 확인한다.
if (!this.head) {
// 비어있다면, 새로운 노드를 head와 tail로 지정한다.
this.head = newNode;
this.tail = newNode;
// 비어 있지 않다면, null로 되어있을 tail의 next를 새로운 노드로 설정하고 tail을 새로운 노드로 업데이트 한다.
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
Tail에 삽입하는 경우 O(1)이 소요된다. 코드와 시각화를 사용하여 생각하면 이해하기가 쉬웠다. (Visualgo 혹은 내가 들은 Udemy 강의를 추천한다 아래 참조에 첨부)
▶︎ Tail에 넣고 싶은 새로운 노드를 생성한다. 현재 Tail로 설정된 노드의 next에 새로운 노드를 연결한다. Tail을 새로운 노드로 설정한다.
pop
✔️ 고려해보아야할 점
node가 0개일 경우, 1개일 경우, 2개 이상인 경우?
// pop - 마지막 요소를 제거 | value에 상관없이 마지막 요소를 제거하면 된다.
pop() {
// 제거할 node가 없을 경우 undefined를 반환한다.
if (!this.head) return undefined;
// Linked list의 경우 마지막 Node를 인덱스로 지정해서 pop할 수 없기 때문에 next가 null일 때까지(tail에 다다를때까지) 차례로 순회해야한다.
let temp = this.head;
let pre = this.head;
// temp와 pre 변수를 우선 head로 부터 시작하게 설정한다.
while (temp.next) {
// next가 null이 될때까지
pre = temp; // pre는 temp를 뒤따라간다
temp = temp.next; // temp는 next node로 이동한다. [그림 1 참고]
}
// [그림 2 참고]
this.tail = pre; // pre를 tail node로 설정한다.
this.tail.next = null; // tail에 지정된 next를 끊는다.
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return temp;
}
}
unshift
✔️ 고려해보아야할 점
Node의 존재 유무? 없을 경우엔 어떻게 할 것이고, 있을 경우엔 어떻게 해주면 될까?
push랑 상당히 비슷하다! 대신 앞쪽에 추가해야 된다는 점을 생각해 보자 🤔 tail이 아닌 head가 중요하겠다!
// value를 받아서 제일 앞쪽에 노드를 추가하려 한다.
unshift(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
// push와 다른 점🌟 : 새로운 Node의 next 노드로 기존의 head를 연결지어주고, 새로운 Node를 head로 업데이트 해준다.
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
Head에 삽입insert하는 경우 O(1)이 소요된다. 과정을 시각화하면서 코드를 생각하면 잘 이해되었다.
나는 이런 식으로 나열해보았다.
▶︎ 노드를 생성한다, 새 노드의 next를 head로 설정해주고 head를 새 노드로 설정해준다.
shift
✔️ 고려해보아야 할 점
node가 0개일 경우, 1개 이상일 경우?
// 첫 번째 노드를 제거하려 한다.
shift() {
// 리스트가 비어 있다면 undefined를 반환한다.
if (!this.head) return undefined;
// 현재 head가 가리키는 노드를 temp에 저장한다.
let temp = this.head;
// head를 다음 노드로 업데이트하여 첫 번째 노드를 삭제한다.
this.head = this.head.next;
// temp가 현재 리스트에서 떨어지도록 next를 null로 설정한다.
temp.next = null;
this.length--;
// 리스트의 길이가 0이 된다면 tail도 null로 설정한다. (빈 상태를 명확하게 설정)
if (this.length === 0) {
this.tail = null;
}
return temp;
}
Head에 있는 노드를 제거하는 것도 O(1)이 소요된다.
▶︎ head에 변수 temp를 선언해주고 head는 temp의 next로 옮긴다. temp next를 끊는다.
get
✔️ 고려해보아야할 점
인덱스의 유효 범위(음수이거나, 리스트의 길이가 크거나 같을 경우?) 설정하기
인덱스를 값으로 받고, 해당 위치의 노드를 찾아가는 과정을 수행해야 함!
// Linked List에서 주어진 index에 해당하는 node의 value를 반환하려 한다.
get(index) {
// 음수이거나 리스트의 길이보다 크거나 같을 경우 undefined를 반환한다.
if (index < 0 || index >= this.length) return undefined;
// temp 변수를 선언하고, head부터 주어진 index까지 순회한다.
let temp = this.head;
for (let i = 0; i < index; i++) {
// for 루프를 사용하여 temp 변수를 해당 인덱스에 위치한 노드로 이동시킨다.
temp = temp.next;
}
return temp.value;
}
조회를 위해선 결국 head부터 시작하여 해당 인덱스를 찾기 위해 순회해야 한다. 고로 Get의 경우에 O(n)이다.
set
✔️ 고려해보아야 할 점
주어진 인덱스가 존재할 경우, 해당하는 노드가 없을 경우(찾지 못한 경우)?
// 특정 인덱스에 해당하는 노드의 값을 변경하려 한다.
set(index, value) {
// 주어진 인덱스에 해당하는 노드를 찾는다. get 메서드 사용
let temp = this.get(index);
// 노드가 존재할 경우? (temp가 null이 아닌 경우)
if (temp) {
// 노드의 값을 주어진 값으로 변경한다.
temp.value = value;
// 변경 성공 (true 반환)
return true;
}
// 주어진 인덱스에 해당하는 노드가 없을 경우 false
return false;
}
Set의 시간 복잡도는 Get 메서드의 시간 복잡도에 의존한다. 주어진 Index에 해당하는 노드를 찾기 위해 Get을 사용하고, 이후에 값을 변경한다. 고로 Set의 시간 복잡도 또한 O(n)이다.
insert
✔️ 고려해보아야할 점
인덱스가 0일 경우, 인덱스가 리스트의 길이와 동일할 경우, 그 외의 경우!
// 특정 인덱스에 새로운 노드를 삽입하려 한다. index와 해당 인덱스에 넣은 value를 받는다.
insert(index, value) {
// index가 0인 경우, 리스트의 맨 앞에 노드를 삽입한다. 이전에 사용한 unshift를 사용한다
if (index === 0) return this.unshift(value);
// index가 리스트의 길이와 동일한 경우 리스트의 맨 뒤에 노드를 삽입한다. 이전에 사용한 push를 사용한다
if (index === this.length) return this.push(value);
// 인덱스가 유효한 범위가 아닌 경우 false를 반환.
if (index < 0 || index > this.length) return false;
// 삽입할 새로운 노드를 생성
const newNode = new Node(value);
// 인덱스 이전 노드를 찾아 temp 변수에 저장
let temp = this.get(index - 1);
// 이전 노드의 next를 새로운 노드의 next로 설정한다.[그림 3 참고]
newNode.next = temp.next;
// 이전 노드의 next를 새로운 노드로 설정하여 연결한다.[그림 4 참고]
temp.next = newNode;
this.length++;
return true;
}
}
head나 tail이 아닌, 중간 삽입의 경우 해당 요점에 도달하기 위해 순회를 필요로 하기 때문에 O(n)이다.
remove
✔️ 고려해보아야할 점
이 또한 유효범위 체크! 인덱스가 0인 경우, 리스트 길이의 -1인 경우, 유효범위에 해당하지 않는 경우
// 특정 인덱스에 해당하는 노드를 제거하려 한다.
remove(index) {
// 인덱스가 0인 경우, 리스트의 맨 앞의 노드를 제거
if (index === 0) return this.shift();
// 인덱스가 리스트의 길이 - 1인 경우, 리스트의 맨 뒤의 노드를 제거, 이전에 만든 pop을 사용한다.
if (index === this.length - 1) return this.pop();
// 인덱스가 유효한 범위가 아닌 경우, 제거 실패 (undefined 반환)
if (index < 0 || index >= this.length) return undefined;
// 제거할 노드의 이전 노드를 찾아 변수 before에 저장한다
let before = this.get(index - 1);
// 제거할 노드를 temp에 저장한다.
const temp = before.next;
// 이전 노드의 next를 제거할 노드의 next로 설정하여 연결을 끊는다. [그림 5 참고]
before.next = temp.next;
// 제거할 노드의 next를 null로 설정하여 노드를 독립시킨다. [그림 6 참고]
temp.next = null;
this.length--;
return temp;
}
중간 노드 삭제의 경우에도 순회를 해야하기 때문에 O(n)이다.
+ 01.28 피드백 추가 사항
블로그에 대한 내용으로 좋은 피드백을 받게 되어서 관련한 내용을 추가하려 한다.
int indexOf<ENTRY>(const ENTRY entry)
Iterable<ENTRY> filter<ENTRY>(bool function(ENTRY entry))
등을 지원하려면 어떻게 해야할까? 관련해서도 생각해보면 좋을꺼같아요
1. indexOf를 Linked List에 적용하려면 어떻게 해야할까?
✔️ indexOf()
배열 또는 문자열에서 주어진 요소를 찾을 수 있는 첫 번째 인덱스를 반환하고, 찾을 수 없는 경우 -1을 반환한다.
처음에는 단순하게 노드에 index 속성 추가해서,, 노드 추가할 때 ++ 되게 하면 안되는 것인가? indexOf시 순회하지 않아도되잖아! 하다가 그렇게 되면 노드가 많아질 경우 메모리 이슈, 삽입 삭제시 과도한 연산 비용이 생기기에.. 필요시에 순회하는 게 낫겠다고 생각하게 되었다.
*push 함수가 만들어져있다고 가정한다.
indexOf(entry) {
// 임시 변수 temp를 선언하고 head를 향하게 한다.
let temp = this.head;
// index 값으로 쓸 변수 선언해주기
let index = 0;
// 순회
while (temp !== null) {
if (temp.value === entry) {
// temp의 value가 entry 값과 같게 된다면 해당하는 index 값을 반환한다.
return index;
}
// temp의 value가 entry값과 같지 않다면 순회를 계속한다.
temp = temp.next;
// 순회하면서 index값을 더해준다.
index++;
}
return -1;
}
function test() {
let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.push(3);
console.log(myLinkedList.indexOf(1));
}
test();
// 0
2. filter()를 Linked List에 적용하려면 어떻게 해야할까?
✔️ filter()
배열에서 주어진 함수의 조건을 만족하는 모든 요소를 추출하여 새로운 배열을 생성한다. 배열을 순회하면서 각 요소에 대해 주어진 함수를 호출하고 true를 반환하는 경우에만 해당 요소를 결과 배열에 포함시킨다.
우선 Linked list가 만들어져 있게 되고, filter속의 주어진 조건에 따라 순회하면서 필터딩된 요소만 새로운 Linked list에 추가해야 한다!
*push 함수가 만들어져있다고 가정한다.
filter(callback) {
// 임시 변수 temp가 현재 노드를 가리키게 한다.
let temp = this.head;
// 필터링된 요소를 넣기 위한 리스트 생성
let newList = new LinkedList();
// temp가 존재하는 동안 반복
while (temp) {
// value가 콜백함수에 의해 true로 평가될 경우
if (callback(temp.value)) {
// 새로운 리스트에 push
newList.push(temp.value);
}
// false일 경우 다음 노드로
temp = temp.next;
}
// temp가 없을 경우 만들어진 새로운 리스트를 반환한다.
return newList;
}
function test() {
let myLinkedList = new LinkedList(0);
myLinkedList.push(1);
myLinkedList.push(2);
myLinkedList.push(3);
myLinkedList.push(4);
// 조건은 2의 배수
console.log(myLinkedList.filter((value) => value % 2 === 0));
}
test();
string도 당연히 가능했는데 연산 시간이 눈에 띄게 훨씬 오래 걸렸다.🤔
자료구조에 대한 정보를 보다보면 경우에 따른 시간 복잡도를 표로 만들어 비교한 것을 자주 접하게 된다. 그때마다 무슨 말인고.. 했다. 왜 저렇게 되는 지? 둘을 비교해서 어떻게 코드로 구현되는지가 모호하게만 느껴졌다.
시간복잡도에 대한 개념을 외우려고만 하다보니 코드와 연결을 못지었다는 것을 깨닫게 되었다. 차근차근 흐름을 이해하려고 시각화 툴도 이용하고 주석도 달고 하다보니.. 머릿속으로 잘 들어오게 됨..!
Trade off! 장점이 존재하면 단점도 존재한다
트레이드오프는 어떤 특성이 좋아지면 다른 특성이 나빠지는 상황을 의미한다. 간단하게 적었지만, Array와 비교해 보았던 부분 역시 두 자료구조를 알아두고 트레이드오프를 이해하기 위해서이다. 장점과 단점의 미묘한 균형을 이해할 수 있어야 올바른 선택을 할 수 있을 것이다. linked list만 알아보았지만 차근차근 하나씩 익혀가면서 문제 해결을 위해 어떤 자료구조가 적절한지 베스트 케이스를 걸러낼 수 있는 스스로가 되길 바란다!
[Traversing Linked Lists In Javascript]
[How Does a Linked List Work? A Beginner's Guide to Linked Lists]
[Udemy - JavaScript Data Structures & Algorithms + LEETCODE Exercises]
Linked List 시각화는 Visualgo를 사용하였습니다.
'Software Engineering' 카테고리의 다른 글
| Difference between Process and Thread (+ Program) (0) | 2024.04.04 |
|---|---|
| MVC Pattern의 본질, GUI, 관심사의 분리, 파생된 아키텍처 패턴 알아보기 (4) | 2023.10.20 |
| 프레임워크와 라이브러리의 차이점, Inversion of Control과 Dependency Injection (0) | 2023.09.10 |
| Imperative 명령형, Declarative Programming 선언형 프로그래밍 (0) | 2023.09.09 |