[ 선형 자료구조 ] 연결 리스트 구현

김수연·2022년 9월 21일
Nodelinkedlist선형 자료구조연결리스트
0

자료구조 / 알고리즘

목록 보기
15/16
post-thumbnail

연결 리스트 (Linked List)

Prototype Object 와 prototype 속성을 기억하면서 메서드를 직접 구현해보자

# Node(), LinkedList()

function Node(data){
	this.data = data;
  	this.next = null;
}

function LinkedList(){
	this.head = null;
  	this.length = 0;
}

node:

  • 값과 포인터가 저장된 덩어리로 생각하면 된다.
  • Node 함수로 만들어지는 객체로부터 data값을 받아온다.

linkedlist:

  • 노드가 연결, 연결되면서 만들어지는 리스트
  • 각 노드가 가진 포인터가 다음 노드를 가리키면서 만들어진다.
  • 노드가 하나도 연결되지 않으면 head값은 null, 길이는 0이 된다.

# size, isEmpty

연결리스트에 노드가 몇 개 있는지 확인하는 size메서드와
연결리스트가 비었는지 확인하는 isEmpty메서드는 만들어 보자

function Node(data){
	this.data = data;
  	this.next = null;
}

function LinkedList(){
	this.head = null;
  	this.length = 0;
}

// 연결리스트의 노드 개수 반환
LinkedList.prototype.size = function(){
	return this.length;
}

// 연결리스트가 비었는지 확인
LinkedList.prototype.isEmpty = function () {
	return this.length === 0;
}

let ll = new LinkedList();
console.log(ll) // LinkedList { head: null, length: 0 }

ll.head = new Node(123);
ll.length++;
console.log(ll); // LinkedList { head: Node { data: 123, next: null }, length: 1 }

# printNode, append

function Node(data){
	this.data = data;
  	this.next = null;
}

function LinkedList(){
	this.head = null;
  	this.length = 0;
}

LinkedList.prototype.size = function(){
	return this.length;
}

LinkedList.prototype.isEmpty = function () {
	return this.length === 0;
}

// 연결리스트의 노드를 순서대로 출력
LinkedList.prototype.printNode = function () {
    for(let node = this.head; node != null; node = node.next){
        process.stdout.write(`${node.data} -> `);
    }

    console.log('null');
}

// 연결리스트의 마지막에 노드 추가
LinkedList.prototype.append = function(data){
    let node = new Node(data),
        current = this.head

	if(this.head === null){
        this.head = node;
    }else{
        while(current.next != null){
            current = current.next;
        }
        current.next = node;
    }

    this.length++;
}

let ll = new LinkedList();
ll.append(1);
ll.append(10);
ll.append(100);
ll.printNode(); /// 1 -> 10 -> 100 -> null
console.log(ll.size()); // 3

# insert

function Node(data){
	this.data = data;
  	this.next = null;
}

function LinkedList(){
	this.head = null;
  	this.length = 0;
}

LinkedList.prototype.size = function(){
	return this.length;
}

LinkedList.prototype.printNode = function () {
    for(let node = this.head; node != null; node = node.next){
        process.stdout.write(`${node.data} -> `);
    }

    console.log('null');
}

// position 위치에 노드 추가
LinkedList.prototype.insert = function (data, position = 0) {
    if(position < 0 || position > this.length){
        return false;
    }
    let node = new Node(data),
        current = this.head,
        count = 0,
        prev;

    if(position === 0){
        node.next = current;
        this.head = node;
    }else{
        while(count++ < position){
            prev = current;
            current = current.next;
        }
        node.next = current;
        prev.next = node;        
    }

    this.length++;

    return true;
}

let ll = new LinkedList();

ll.insert(1);
ll.insert(10); 
ll.insert(100);
ll.printNode();

ll.insert(2,1);
ll.insert(3,3);
ll.printNode();
console.log(ll.size());
while(count++ < position){// while(count != position), count++; 
	prev = current;
    current = current.next;
}
node.next = current;
prev.next = node;

주석처리한 부분처럼 나눠서 적기 보다 count++ < position 으로 합쳐서
적으면 더 보기 간편하고 좋다.

# remove

function Node(data){
	this.data = data;
  	this.next = null;
}

function LinkedList(){
	this.head = null;
  	this.length = 0;
}

LinkedList.prototype.size = function(){
	return this.length;
}

LinkedList.prototype.printNode = function () {
    for(let node = this.head; node != null; node = node.next){
        process.stdout.write(`${node.data} -> `);
    }

    console.log('null');
}

// position 위치에 노드 추가
LinkedList.prototype.insert = function (data, position = 0) {
    if(position < 0 || position > this.length){ // 말도 안되는 경우를 false로 리턴
        return false;
    }
    let node = new Node(data),
        current = this.head,
        count = 0,
        prev;

    if(position === 0){
        node.next = current;
        this.head = node;
    }else{
        while(count++ < position){
            prev = current;
            current = current.next;
        }
        node.next = current;
        prev.next = node;        
    }

    this.length++;

    return true;
}

// remove() data를 찾아서 노드 삭제 
LinkedList.prototype.remove = function (data){
    let current = this.head,
        prev;
    
    // 지우고 싶은 노드 찾기
    while(current.data != data && current.next != null){ 
        prev = current;
        current = current.next;
    } 

    // 다 돌았는데 찾는 노드 없으면 null
    if(current.data != data){ // 다음 노드가 더이상 없어서 위의 while문이 끝났는데 여전히 현 노드의 값이 찾는 값과 같지 않으면 null 반환
        return null;
    }

    if(current == this.head){ // 첫 노드인 경우 prev = current, current = this.head 로 prev, current 둘 다 같은 값을 가리키게 되므로 오류 생김 -> 따로 처리
        this.head = current.next; 
    }else{
        prev.next = current.next; 
    }

    this.length--;

    return current.data;
}

let ll = new LinkedList();

ll.insert(1);
ll.insert(10); 
ll.insert(100);
ll.insert(2,1);
ll.insert(3,3);
ll.printNode();

console.log(ll.remove(1000)); // null
ll.printNode();
console.log(ll.remove(1));
ll.printNode();
console.log(ll.remove(2));
ll.printNode();
console.log(ll.remove(100));
ll.printNode();
console.log(ll.size());

this.head == null 이면 current.next == null 이기 때문에 따로 잡을 필요가 없다.

9.22 더 추가 예정 removeAt(), indexOf()

# removeAt

function Node(data){
	this.data = data;
  	this.next = null;
}

function LinkedList(){
	this.head = null;
  	this.length = 0;
}

LinkedList.prototype.size = function(){
	return this.length;
}

LinkedList.prototype.printNode = function () {
    for(let node = this.head; node != null; node = node.next){
        process.stdout.write(`${node.data} -> `);
    }

    console.log('null');
}


LinkedList.prototype.insert = function (data, position = 0) {
    if(position < 0 || position > this.length){
        return false;
    }
    let node = new Node(data),
        current = this.head,
        count = 0,
        prev;

    if(position === 0){
        node.next = current;
        this.head = node;
    }else{
        while(count++ < position){
            prev = current;
            current = current.next;
        }
        node.next = current;
        prev.next = node;        
    }

    this.length++;

    return true;
}

LinkedList.prototype.remove = function (data){
    let current = this.head,
        prev;
    
    while(current.data != data && current.next != null){
        prev = current;
        current = current.next;
    } 
  
    if(current.data != data){ 
        return null;
    }

    if(current == this.head){
        this.head = current.next; 
    }else{
        prev.next = current.next; 
    }

    this.length--;

    return current.data;
}

//해당 인덱스의 노드 삭제
LinkedList.prototype.removeAt = function (position){
    if(position < 0 || position >= this.length){
        return null;
    }

    let current = this.head,
        count = 0,
        prev;
    
    while(count++ < position){
        prev = current;
        current = current.next; 
    }

   if(current == this.head){
        this.head = current.next;
   }else{
        prev.next = current.next;
   }

   this.length--;

   return current.data;
}

let ll = new LinkedList();

ll.insert(1);
ll.insert(10); 
ll.insert(100);
ll.insert(2,1);
ll.insert(3,3);
ll.printNode();
console.log('----------------------------------');

console.log(ll.removeAt(1000));
ll.printNode();
console.log(ll.removeAt(1));
ll.printNode();
console.log(ll.removeAt(2));
ll.printNode();
console.log(ll.removeAt(100));
ll.printNode();
console.log(ll.size());
 if(position < 0 || position >= this.length){
        return null;
    }
  • 노드 추가 (insert)와 다르게 position == this.length인 경우도 null로 리턴:
    마지막 요소 다음에 끼워넣는 경우 this.length와 값이 같지만
    기존에 있는 노드에서 삭제하는 경우 this.length를 인덱스로 갖는 노드는 없기 때문이다.

# indexOf, remove2

function Node(data){
	this.data = data;
  	this.next = null;
}

function LinkedList(){
	this.head = null;
  	this.length = 0;
}

LinkedList.prototype.size = function(){
	return this.length;
}

LinkedList.prototype.printNode = function () {
    for(let node = this.head; node != null; node = node.next){
        process.stdout.write(`${node.data} -> `);
    }

    console.log('null');
}

LinkedList.prototype.insert = function (data, position = 0) {
    if(position < 0 || position > this.length){
        return false;
    }
    let node = new Node(data),
        current = this.head,
        count = 0,
        prev;

    if(position === 0){
        node.next = current;
        this.head = node;
    }else{
        while(count++ < position){
            prev = current;
            current = current.next;
        }
        node.next = current;
        prev.next = node;        
    }

    this.length++;

    return true;
}

LinkedList.prototype.remove = function (data){
    let current = this.head,
        prev;
  
    while(current.data != data && current.next != null){
        prev = current;
        current = current.next;
    } 

    if(current.data != data){
        return null;
    }

    if(current == this.head){
        this.head = current.next; 
    }else{
        prev.next = current.next; 
    }

    this.length--;

    return current.data;
}

//해당 인덱스의 노드 삭제
LinkedList.prototype.removeAt = function (position){
    if(position < 0 || position >= this.length){
        return null;
    }

    let current = this.head,
        count = 0,
        prev;
    
    while(count++ < position){
        prev = current;
        current = current.next; 
    }

   if(current == this.head){
        this.head = current.next;
   }else{
        prev.next = current.next;
   }

   this.length--;

   return current.data;
}

// data 값을 갖는 노드의 인덱스 리턴 
LinkedList.prototype.indexOf = function(data){
    let current = this.head,
        count = 0;

   while(current != null){ //끝까지 돌았는데 노드가 null인 경우 -1 리턴
        if(current.data === data){
            return count;
        }

        count++;
        current = current.next;
   }

   return -1;
}

// data에 해당하는 노드의 인덱스를 이용해서 노드 지우는 메서드
LinkedList.prototype.remove2 = function (data){
    let index = this.indexOf(data);
    return this.removeAt(index);
}

let ll = new LinkedList();

ll.insert(1);
ll.insert(10); 
ll.insert(100);
ll.insert(2,1);
ll.insert(3,3);
ll.printNode();

console.log(ll.indexOf(1000)); // -1
console.log(ll.indexOf(1)); // 4
console.log(ll.indexOf(2)); // 1
console.log(ll.indexOf(100)); // 0

console.log(ll.remove2(1000)); // null
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> 1 -> null
console.log(ll.remove2(1)); // 1
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> null
console.log(ll.remove2(2)); // 2
ll.printNode(); // 100 -> 10 -> 3 -> null
console.log(ll.remove2(100)); // 100
ll.printNode(); // 10 -> 3 -> null
console.log(ll.size()); // 2
  • 크게 루프안에 해당 data가 없는 경우를 while로 잡아냄
  • while 내에서 현재 노드의 값이 data와 같지 않으면 count(인덱스)와
    현 노드를 업데이트 함
  • 현 노드의 값이 data와 같으면 count리턴
profile
김수연
길을 찾고 싶은 코린이 of 코린이
이전 포스트

프로토 타입 prototype

다음 포스트

[ 선형 자료구조 ] 이중 연결 리스트 구현하기

0개의 댓글