What I Learned
  • Introduction
  • Introduction
  • Javascript
    • 클로저 (closure)
    • 프로토타입 (Prototype)
    • 정규표현식 (RegExp)
    • 날짜 (Date)
    • jQuery 분석
    • 스코프 (this)
    • 성능 최적화 (Optimization)
  • Style
    • CSS
      • Prevent user select
      • Aspect Ratio
      • Sticky Footer
    • SASS
      • for loop
      • mixin example
      • Media Query
  • Web
    • 웹의 동작 과정
    • Cross Browser
    • Document Reflows
    • Open Graph
    • 이미지 압축 (Image optimization)
    • SPA, SSR 비교
  • Algorithm and Data Structure
    • 자료구조 (Data Structure)
      • 큐 (Queue)
      • 스택 (Stack)
      • 링크드 리스트 (Linked List)
    • 기초 이론
      • 복잡도 분석
    • 수학 (Math)
      • factorial (계승)
      • 피보나치 수 (Fibonacci)
    • 정렬 (Sorting)
      • 버블 정렬 (Bubble Sort)
      • 선택 정렬 (Selection Sort)
      • 삽입 정렬 (Insertion Sort)
      • 합병 정렬 (Merge Sort)
      • 퀵 정렬 (Quick Sort)
    • 탐색 (Search)
      • 순차 탐색 (linear search)
      • 이진 탐색 (Banary search)
    • 문제 풀이
      • 땅따먹기
      • 가장 큰 원소의 합 구하기
      • JS with HTML
  • Software Engineering
    • OOP
    • Development Process
    • TDD / BDD
  • Interview
    • HTML
    • CSS
    • Javascript
    • Other
    • General Questions
  • DevOps
    • gulp
  • PHP
    • Basic
Powered by GitBook
On this page
  1. Algorithm and Data Structure
  2. 자료구조 (Data Structure)

링크드 리스트 (Linked List)

링크드리스트는 데이터 요소들의 선형 콜렉션이다. 메모리에서 물리적으로 정렬되어있는 선형을 말하는 것이 아니라 각각의 요소는 다음 포인트에 대한 정보를 가지고 있다. 각 노드는 연속으로 구성되어있다. 이 구조는 효과적으로 요소를 삽입, 삭제할 수 있다.

Previous스택 (Stack)Next기초 이론

Last updated 6 years ago

노드로 사용할 클래스 정의

class Node {
    constructor(value, next = null) {
        this.value = value;
        this.next = next;
    }

    toString(callback) {
        return this.value;
    }
}

링크드리스트 클래스 정의

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }

    add (value) {
        const newNode = new Node(value);

        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            return this;
        }

        // 링크드리스트의 마지막 데이터 tail에 새 노드를 지정한다.
        this.tail.next = newNode;
        this.tail = newNode;
        return this;
    }

    remove(pointer) {
        if (!this.head) { return null; }

        let current = this.head;
        let before;
        let remove;
        let count = 0;

        if (pointer === 0) { // 첫 노드를 삭제
            remove = this.head;
            this.head = this.head.next;
            return remove;
        } else {
            while (count < pointer) {
                // 해당 포지션까지 이동해서 삭제
                before = current;
                remove = current.next;
                count++;
                current = current.next;
            }

            if (this.tail.value === remove.value) {
                this.tail = current;
            }

            before.next = remove.next;
            return remove;
        }
    }

    search (pointer) {
        let current = this.head;
        let count = 0;
        while (count < pointer) { // pointer 위치로 이동
            current = current.next;
            count++;
            console.log(current);
        }

        if (!current) {
            console.log("There is no result.");
            return false;
        }

        return current.value;
    }

    removeHead() {
        if (!this.head) { return null; }

        const deletedHead = this.head;

        if (this.head.next) {
            this.head = this.head.next;
        } else {
            this.head = null;
            this.tail = null;
        }

        return deletedHead;
    }

    toArray() {
        const nodes = [];
        let currentNode = this.head;
        while (currentNode) {
            nodes.push(currentNode);
            currentNode = currentNode.next;
        }
        return nodes;
    }

    toString() {
        return this.toArray().map(node => node.toString()).toString();
    }
}
Linked List