자바스크립트를 이용한 싱글 링크드리스트 구현

Soly; 독특하게·2020년 12월 2일

JavaScript

목록 보기

3/7

Data Type : integer
기능 : Tail Add, Tail Remove, Search change, Search remove, Ascending Sort(오름차순 정렬)

링크드리스트 이론

왜 필요한지? 배열과 비교하기

배열) 반복적 접근성 가짐 + 선언 쉬움

BUT!

정렬되어 있는 배열에 새로운 데이터를 넣기 위해 많은 반복 작업이 필요합니다.
정렬을 시키는 것 조차도 불편합니다.(링크드리스트도 같은 불편함 가짐)

링크드리스트) 각 노드들 (동적할당 된 데이터들)이 포인터로 연결되어 있습니다

따라서, 새로운 데이터를 동적할당해서 넣기 때문에 서로 연결만 수정 하면 됩니다.

장점 : 배열에 비해 추가, 삭제 용이 합니다.
단점 : 순차탐색으로 탐색속도가 느립니다.

프로그래머의 판단)

탐색, 정렬 ⇒ 배열
추가, 삭제 ⇒ 링크드리스트

기능 이해

링크드리스트 노드 생성

링크드리스트)

class component로 작성 ) lifecycle 사용하는 프로젝트의 연장선으로 선택했습니다.

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

문제 : 자바스크립트는 함수 호출 시 call by value가 되버려, sort에서 정렬된 값을 저장하지 않습니다.
따라서, head부분에 빈 노드를 할당 해주었습니다

class LinkedList {
	constructor() {
		this.head = new Node();
	}
}

빈 노드 생성

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

데이터 삽입

목표: 끝 부분에 값을 넣기

tailPush(value) {
	const node = new Node(value);
	let currNode = this.head;
	while (currNode.next) {
		currNode = currNode.next;
	}
	currNode.next = node;
    }

새로운 노드를 만들고 / 변수 curNode에 head를 넣어주었습니다.
while ) head의 다음이 없을때까지 - 링크드리스트의 끝까지 돌면서
마지막 노드가 되면 조건문을 빠져나오는데, 이때 새로운 노드를 가리키도록 했습니다.

데이터 삭제

목표: 끝 부분에 값을 삭제

tailDelete() {
  let currentNode = this.head;
  if (currentNode.next == null) {
    console.log("No Node")
    return;
  }
  while (currentNode.next.next) {
    currentNode = currentNode.next;
  }
  currentNode.next = null;
};

새로운 노드를 만들고 / 변수 curNode에 head를 넣어주었습니다.
if ) 노드가 없다면 "No Node"를 출력하도록 했습니다.
while ) head의 다음이 없을때까지 - 링크드리스트의 끝까지 돌면서
마지막 노드가 되면 조건문을 빠져나오는데, 이때 null을 가리키도록 했습니다.

데이터 찾아 삭제

목표: 삭제하고자 하는 데이터 입력받아, 삭제
(단, 중복된 값을 갖고 있다면 처음 값 만 제거)

searchValueToDelete(value) {
  //중복시 처음 것 만 제거
  let currentNode = this.head;
  while (currentNode.next !== null) {
    if (currentNode.next.value === value) {
      let delNode = currentNode.next;
      if (delNode.next != null) {
        currentNode.next = delNode.next;
        return;
      } else {
        currentNode.next = null;
        return;
      }
    }
    currentNode = currentNode.next;
  }
  if (currentNode.next === null) {
    console.log("No search value delete")
  }
};

값이 없다면 "No search value delete"가 출력됩니다.

변수 currNode에 head를 넣어주고
while ) head의 다음이 없을때까지 - 링크드리스트의 끝까지 돌면서
-head의 다음 값과 입력받은 값이 같으면 / 다음 값을 삭제
-중간노드를 삭제한다면 삭제할 노드의 다음노드를 가르켜야 합니다.
+) 중간노드 = 삭제할 노드의 다음노드가 존재할 경우입니다. 즉, 처음노드도 포함
-마지막 노드를 삭제한다면 다음 노드는 null을 가르키도록 했습니다.

데이터 찾고 값 바꾸기

목표: 링크드리스트에 있는 값을 다른 값으로 바꾸기

searchValueToChange = (value, changeValue) => {
  //중복시 처음 것 만 바꾸기
  let currentNode = this.head
  while (currentNode.value !== value) {
    currentNode = currentNode.next
    if (currentNode === null) {
      console.log("No search value change")
      return
    }
  }
  currentNode.value = changeValue
}

원하는 값이 있는 노드를 찾아서 '값'만 바꾸도록 했다.
단, 중복시 처음 것 만 바꾸도록 해주었다.
원하는 값이 있는 노드가 없다면 "No search value change"를 출력하도록 했습니다.

변수 currNode에 head를 넣어주고
if ) 현재 노드 값과 바꿀 값이 일치하면 값을 바꾸었습니다.
while ) 현재 노드 값과 바꿀 값이 일치할 때까지 - 링크드리스트의 끝까지 돌기

데이터 정렬

목표: 이미 값이 넣어져 있는 링크드 리스트를 오름차순으로 정렬

ascendingSort() {
  let countNode = this.head.next;
  let currentNode = this.head.next;
  let count = 0
  while (countNode !== null) {
    countNode = countNode.next
    count++
  }
  while (count) {
    while (currentNode.next !== null) {
      if (currentNode.next.value < currentNode.value) {
        this.changeToNextNode(currentNode.next, currentNode);
      }
      currentNode = currentNode.next
    }
    currentNode = this.head.next
    count--
  }
  this.print()
};

현재 값과 다음값의 자리를 바꿔준다 ?
노드에 따로 함수를 생성해서 넣어주었다.
이 함수는 단순히 값을 바꿔 주는 함수이다.

changeToNextNode(next, current) {
    var temp = next.value
    next.value = current.value
    current.value = temp
}

링크드리스트 실습

원하는 결과

const newList = new LinkedList();
newList.tailPush(5);
newList.tailPush(1);
newList.tailPush(6);
newList.tailPush(3);
newList.tailPush(4);
newList.tailPush(8);
newList.tailPush(7);
newList.print(); // 링크드리스트 출력

결과)

처음 결과 ) 5 -> 1 -> 6 -> 3 -> 4 -> 8 -> 7 ->
마지막 노드 삭제 ) 5 -> 1 -> 6 -> 3 -> 4 -> 8 ->
원하는 값(3) 삭제 ) 5 -> 1 -> 6 -> 4 -> 8 -> 7 ->
원하는 값(3)을 바꾸기(10) ) 5 -> 1 -> 6 -> 1000 -> 4 -> 8 -> 7 ->
오름차순 정렬 ) 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ->

최종 코드 작성

head부분에 빈 노드를 할당해주니 코드가 간결해졌다.

class LinkedList {
    constructor() {
        this.head = new Node();
    }
    tailPush(value) {
        const node = new Node(value);
        let currentNode = this.head;
        while (currentNode.next) {
            currentNode = currentNode.next;
        }
        currentNode.next = node;
    }
    tailDelete() {
        let currentNode = this.head;
        if (currentNode.next == null) {
            console.log("No Node")
            return;
        }
        while (currentNode.next.next) {
            currentNode = currentNode.next;
        }
        currentNode.next = null;
    };
    searchValueToDelete(value) {
        //중복시 처음 것 만 제거
        let currentNode = this.head;
        if (currentNode.next == null) {
            console.log("No search value delete")
            return;
        }
        while (currentNode.next !== null) {
            if (currentNode.next.value === value) {
                let delNode = currentNode.next;
                if (delNode.next != null) {
                    currentNode.next = delNode.next;
                    return;
                } else {
                    currentNode.next = null;
                    return;
                }
            }
            currentNode = currentNode.next;
        }
    };
    searchValueToChange = (value, changeValue) => {
        //중복시 처음 것 만 바꾸기
        let currentNode = this.head
        if (currentNode.value == null) {
            console.log("No search value change")
            return;
        }
        while (currentNode.value !== value) {
            currentNode = currentNode.next
        }
        currentNode.value = changeValue
    }
    ascendingSort() {
        var countNode = this.head.next;
        var count = 0
        while (countNode !== null) {
            countNode = countNode.next
            count++
        }
        var currentNode = this.head.next;
        while (count) {
            while (currentNode.next !== null) {
                if (currentNode.next.value < currentNode.value) {
                    this.changeToNextNode(currentNode.next, currentNode);
                }
                currentNode = currentNode.next
            }
            currentNode = this.head.next
            count--
        }
        this.print()
    };
    changeToNextNode(next, current) {
        var temp = next.value
        next.value = current.value
        current.value = temp
    }
    print() {
        let currentNode = this.head.next;
        while (currentNode !== null) {
            console.log(`${currentNode.value} -> `);
            currentNode = currentNode.next;
        }
        console.log("LinkedList End")
    };
    randomNumbers() {
        for (var i = 0; i < 10; i++) {
            this.tailPush(Math.floor(Math.random() * 100 + 1));
        }
    }
}
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}
const newList = new LinkedList();
newList.randomNumbers()
newList.print();
newList.ascendingSort();

입력받을 수 없나요?

자바스크립트(Node.js)에는 C언어의 scanf, Java의 Scanner와 같이 편리하게 입력할수 있는 시스템이 없습니다.
따라서, 랜덤을 생성하는 함수에 원하는 만큼 값을 입력하면 됩니다.

randomNumbers(number) {
    for (var i = 0; i < number; i++) {
        this.tailPush(Math.floor(Math.random() * 100 + 1));
    }
}

Soly; 독특하게

협업을 즐겨하는 목표지향적인, Front-End 개발자입니다.

이전 포스트

fetch()로 API호출

다음 포스트