Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- javascript
- S&P500
- 미국주식
- 다형성
- 현금흐름표
- 기업분석
- XLF
- 그리디 알고리즘
- 제태크
- 오버라이딩
- FCF
- 접근제어자
- 잉여현금흐름
- 객체지향
- 인플레이션
- 배당성장
- 무디스
- 자바
- object
- StringBuffer
- 금리인상
- 금리인하
- 주린이
- 백준
- Java
- 주식
- 알고리즘
- etf
- mco
- 프로그래머스
Archives
- Today
- Total
오늘의하루
[Javascript] LinkedList 연결 리스트 구현하기 본문
단일 연결 리스트
각 노드에 1개의 자료 공간과 저장공간을 가지며 각 노드의 포인터는 다음 노드를 가리킨다.
자료공간 | 저장공간 | ====> | 자료공간 | 저장공간 | ====> | 자료공간 | 저장공간 |
기본적인 노드 구조
class node {
constructor(data) {
this.data = data;
this.next = null;
}
}
가장 기본적인 노드 구조이며 연결 리스트를 만들때 사용할 용도입니다.
class LikedList {
constructor() {
let init = new node("init");
this.head = init;
this.tail = init;
this.size = 0;
}}
연결리스트의 초기 모습이며, 이때는 처음과 끝 그리고 리스트 갯수를 나타낼수 있는 변수들을 정의 해줍니다.
노드 연결해주기
// 맨 앞에 하나씩 추가하기
unshift(data) {
let newnode = new node(data);
let current = this.head;
newnode.next = current.next;
current.next = newnode;
if(this.tail.data === "init"){
this.tail = newnode;
}
this.size++;
}
unshift라는 함수를 만들었는데 이 함수의 기능은 노드를 가장 앞에 연결해주는 기능을 가지고 있습니다.
// 마지막에 하나씩 추가하기
push(data) {
let newnode = new node(data);
let current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = newnode;
this.tail = newnode;
this.size++;
}
push 함수는 가장 기본적인 노드 연결 방식이며 노드 끝에 새로운 노드를 연결해주는 기능을 가지고 있습니다.
// 원하는 위치에 하나씩 추가하기
insert(data, location) {
let newnode = new node(data);
let current = this.find(location);
newnode.next = current.next;
current.next = newnode;
this.size++;
while (current.next != null) {
current = current.next;
}
this.tail = current;
}
find(location) {
let current = this.head;
while (current.data != location) {
current = current.next;
}
return current;
}
insert 함수는 원하는 위치에 새로운 노드를 연결해주는 기능을 가지고 있습니다.
노드 제거하기
// 앞에꺼 하나씩 제거하기
shift() {
let current = this.head;
current.next = current.next.next;
this.size--;
}
shift 함수는 가장 앞에있는 노드를 제거해주는 기능을 가지고 있습니다.
// 맨뒤에꺼 하나씩 제거하기
pop() {
let current = this.head;
while (current.next.next != null) {
current = current.next;
}
current.next = null;
this.tail = current;
this.size--;
}
pop 함수는 마지막에 있는 노드를 제거해주는 기능을 가지고 있습니다.
// 원하는 위치 하나씩 제거하기
splice(location) {
let current = this.head;
let currentpre = this.head;
let last = this.head;
while (current.data != location) {
current = current.next;
}
while (currentpre.next.data != location) {
currentpre = currentpre.next;
}
currentpre.next = current.next;
while (last.next != null) {
last = last.next;
}
this.tail = last;
this.size--;
}
splice 함수는 원하는 위치의 노드를 제거해주는 기능을 가지고 있습니다.
// 원하는 값 수정하기
change(location, change_value){
let current = this.head;
while(current.data != location){
current = current.next;
}
current.data = change_value;
}
change 함수는 원하는 값을 수정해주는 기능을 가지고 있습니다.
노드의 값을 배열로 받아오기
printArr(){
let current = this.head;
let arr = [];
while(current.next!= null){
arr.push(current.next.data);
current = current.next;
}
return arr;
}
printArr 함수는 연결된 노드의 data 값을 배열로 반환해주는 기능을 가지고 있습니다.
노드의 전체 길이를 받아오기
printLength(){
return this.size;
}
printfLength 함수는 size를 이용하여 전체 길이를 반환해주는 기능을 가지고 있습니다.
전체 코드
class node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LikedList {
constructor() {
let init = new node("init");
this.head = init;
this.tail = init;
this.size = 0;
}
// 맨 앞에 하나씩 추가하기
unshift(data) {
let newnode = new node(data);
let current = this.head;
newnode.next = current.next;
current.next = newnode;
if(this.tail.data === "init"){
this.tail = newnode;
}
this.size++;
}
// 마지막에 하나씩 추가하기
push(data) {
let newnode = new node(data);
let current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = newnode;
this.tail = newnode;
this.size++;
}
// 원하는 위치에 하나씩 추가하기
insert(data, location) {
let newnode = new node(data);
let current = this.find(location);
newnode.next = current.next;
current.next = newnode;
this.size++;
while (current.next != null) {
current = current.next;
}
this.tail = current;
}
find(location) {
let current = this.head;
while (current.data != location) {
current = current.next;
}
return current;
}
// 앞에꺼 하나씩 제거하기
shift() {
let current = this.head;
current.next = current.next.next;
this.size--;
}
// 맨뒤에꺼 하나씩 제거하기
pop() {
let current = this.head;
while (current.next.next != null) {
current = current.next;
}
current.next = null;
this.tail = current;
this.size--;
}
// 원하는 위치 하나씩 제거하기
splice(location) {
let current = this.head;
let currentpre = this.head;
let last = this.head;
while (current.data != location) {
current = current.next;
}
while (currentpre.next.data != location) {
currentpre = currentpre.next;
}
currentpre.next = current.next;
while (last.next != null) {
last = last.next;
}
this.tail = last;
this.size--;
}
// 원하는 값 수정하기
change(location, change_value){
let current = this.head;
while(current.data != location){
current = current.next;
}
current.data = change_value;
}
// 전체 값을 배열로 리턴하기
printArr(){
let current = this.head;
let arr = [];
while(current.next!= null){
arr.push(current.next.data);
current = current.next;
}
return arr;
}
// 전체 길이 리턴하기
printLength(){
return this.size;
}
}
let a = new LikedList();
a.unshift(1); // head : 1 tail : 1
a.unshift(2); // head : 2, 1 tail : 1
a.push(3); // head : 2, 1, 3 tail : 3
a.insert(99,2); // head : 2, 99, 1, 3 tail : 3
a.pop(); // head : 2, 99, 1 tail : 1
a.change(99, 5); // head : 2, 5, 1 tail : 1
a.splice(5) // head : 2, 1 tail : 1
a.shift() // head : 1 tail : 1
let b = a.printArr(); // [1]
let c = a.printLength(); // 1
console.log(a);
'javascript & nodejs' 카테고리의 다른 글
[javascript] 조합, 순열 및 객체 정렬 (0) | 2022.06.23 |
---|---|
[javascript] Call Stack과 Event Loop 알아보기 (0) | 2022.05.22 |
[node js] Module 생성 및 사용 방법 (0) | 2022.05.22 |
Comments