반응형
연결 리스트(LinkedList)
📝연결 리스트란?
- 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
- 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
- 각 요소가 데이터와 다음 요소를 참조하는 정보를 포함하는 노드로 구성된 형태
연결 리스트의 요소
- 노드(Node) : 연결 리스트의 기본 단위로, 데이터와 다음 노드를 가리키는 필드로 구성
- 포인터(pointer) : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 갖고 있는 공간
- 헤드(Head) : 연결 리스트의에서 가장 처음 위치하는 노드. 리스트 전체를 참조하는데 사용
- 테일(Tail) : 연결 리스트의 가장 마지막에 위치하는 노드. 다음 노드가 존재하지 않으므로 링크된 노드의 필드 값은 Null이다.
연결 리스트 구현(JavaScript)
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
append(data) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
}
prepend(data) {
const newNode = new Node(data, this.head);
this.head = newNode;
}
remove(data) {
if (this.head === null) {
return;
}
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next !== null) {
if (current.next.data === data) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
find(data) {
let current = this.head;
while (current !== null) {
if (current.data === data) {
return current;
}
current = current.next;
}
return null;
}
}- 위 코드 구조는 값을 추가하거나, 삭제, 찾는 등의 기능을 수행할 수 있음.
- 단순 연결리스트이므로 "직접적으로" 값을 참조하여 삭제, 추가 기능을 수행할 수 있음.
반응형
불변성(Immutability)
📝불변성이란?
- 데이터 구조나 객체가 생성 이후로 변경되지 않는 것을 의미함.
- 초기 상태에서 값을 변경할 수 없기 때문에 상태 변화가 없음.
- 주로 리액트와 같은 상태(state)를 관리할 때 유리함
- 데 이터가 변경되지 않고 변경 시 복사본을 만들어 수정
- 함수형 프로그래밍에서 중요한 핵심 개념 중 하나.
❓ 함수형 프로그래밍
- 수학적 함수 개념을 바탕으로 하는 프로그래밍 패러다임
- 가독성과 테스트에 매우 용이해지고, 부수적인 효과가 없으므로 병렬처리에 용이함
- 상태변화가 일어나지 않으므로 버그 추적 및 유지보수에 용이
순수 함수(pure Function)
function add(a, b) {
return a + b;
}- 동일한 입력에 대해 항상 동일한 출력을 반환하고 외부 상태를 변경하지 않는 함수
- 테스트, 디버깅에 용이함
클로저 (Closure)
function createCounter() {
let count = 0;
return function() {
count++;
return count;
};
}
const counter = createCounter();
console.log(counter()); // 1
console.log(counter()); // 2- 함수 내부의 변수를 외부에서 접근할 수 없는 객체
- 동적으로 함수 생성이 가능하며, 생성된 함수가 외부 변수를 기억함
고차 함수(Higher-Order Function)
function map(array, fn) {
return array.map(fn);
}
const doubled = map([1, 2, 3], x => x * 2);
console.log(doubled);- map, filter, reduce 등의 함수
- 재사용성을 높히고, 추상화하여 코드의 가독성을 높일 수 있음
- 다만, 복잡성이 증가하여 함수의 흐름 추적이 어려울 수 있음
불변성을 사용하는 이유
- 데이터 흐름을 쫒아가기 용이함(유지보수에 유리함)
- 불변성을 지키면서 데이터를 변화시키면 예상 가능하고 신뢰할 수 있는 코드가 될 수 있음
- 불변성이 가장 많이 적용된 라이브러리가 바로 리액트(state, props 관리)
가변 데이터를 불변 타입으로 구현하기 위한 요소
const person = { name: 'Alice', age: 25 };
const updatedPerson = { ...person, age: 26 };- 객체나 데이터 구조가 생성된 후 변경되지 않고, 필요 시 새로운 객체 생성하여 변화
- 수정시에도 새로운 객체를 생성하여 데이터 이전 상태 보존
- 객체의 일부만 변경할 때, 나머지 부분은 부분 복사하여 재사용 후 새로운 객체 생성
🤔 그렇다면 불변성과 연결 리스트를 합치게 된다면?
👍 장점
- 상태가 변하지 않으므로 코드의 동작 예측이 쉬워지고 디버깅이 용이함
- 상태가 변하지 않으므로 여러 스레드에서 동시 접근해도 안전함
- 재사용성을 고려하므로 복사 및 수정이 용이해짐
- 데이터 흐름이 명확해짐
👎 단점
- 새로운 객체를 생성하므로 메모리 사용량이 증가
- 메모리 사용량이 증가하면서 오버헤드 발생 가능 (최신 JavaScript 엔진은 효율적 메모리를 처리하므로 많은 상황에선 문제 발생하지 않음)
불변 연결 리스트 구현(JavaScript)
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class ImmutableLinkedList {
constructor(head = null) {
this.head = head;
}
append(data) {
const newNode = new Node(data);
if (this.head === null) {
return new ImmutableLinkedList(newNode);
} else {
let current = this.head;
let previous = null;
while (current !== null) {
previous = current;
current = current.next;
}
previous.next = newNode;
return new ImmutableLinkedList(this.head);
}
}
prepend(data) {
const newNode = new Node(data, this.head);
return new ImmutableLinkedList(newNode);
}
remove(data) {
if (this.head === null) {
return this;
}
if (this.head.data === data) {
return new ImmutableLinkedList(this.head.next);
}
let current = this.head;
while (current.next !== null) {
if (current.next.data === data) {
current.next = current.next.next;
return new ImmutableLinkedList(this.head);
}
current = current.next;
}
return this;
}
}- 기존 연결리스트와 다르게 값을 추가 및 제거시 새로운 객체를 반환하는 형태
반응형
댓글