자료구조 ] Linked List

자료구조 ] Linked List

출처 : 생활코딩(https://www.opentutorials.org/module/1335/8821)

정의

노드라는 데이터 묶음이 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

특징 / 특이사항

늘어뜨린 자료의 추가와 삭제의 시간 복잡도 O(1)에 해결된다.

특정 위치의 데이터를 검색하는 데는 O(n)의 시간 복잡도를 가진다.

그래서 데이터 탐색이 많이 필요한 경우에는 Array를, 데이터 삽입과 삭제가 많은 경우에는 linked list를 이용한다.

용어

이름 설명 node 데이터와 포인터 정보가 들어있는 데이터 묶음 head 첫번째 노드 data field 데이터를 담고 있는 부분 link field 다음 노드의 포인트 값을 가지고 있는 부분

Javascript Linked List 구현 방법

먼저 노드 클래스를 구현한다.

class Node { _data; _next; constructor(data, next = null) { this._data = data; this._next = next; } get data() { return this._data; } get next() { return this._next; } set next(node) { this._next = node; } }

노드를 연결할 linked list 클래스를 구현한다.

class LinkedList { _head; _size; _current; constructor() { this._head = null; this._size = 0; this._current = null; } addToTail(data) { const node = new Node(data); // 데이터가 없을 때는 head에만 데이터를 넣어주고 if (!this._head) { this._head = node; // 데이터가 있는 상태에는 next 부분에 다음 노드를 넣어주었다. // 엄밀히 말하면 포인트 구조는 아니다. } else { this._current.next = node; } this._current = node; this._size += 1; } // 저장한 모든 데이터를 가져올 수 있도록 구현 getAllData() { let node = this._head; while (node.next) { console.log(node.data); node = node.next; } console.log(node.data); } }

코드를 구현해보면,

const l = new LinkedList(); l.addToTail('A'); l.addToTail('B'); l.addToTail('C'); l.getAllData();

다음과 같은 결과를 얻는다.

A

B

C

from http://jibsun-i.tistory.com/15 by ccl(A) rewrite - 2021-10-14 15:59:53