[자료구조 with JS] 연결 리스트(Linked List) (2) 삽입, 검색, 삭제

 

 

이전 글: [자료구조 with JS] 연결 리스트(Linked List) (1) 개념과 클래스 

 

 

연결 리스트의 메서드

연결 리스트 메소드 표

 

삽입

insertFisrt(data)

insertFirst(data) {
    this.head = new Node(data, this.head)
}

 

insertAt(data, index)

//Solution 1
insertAt(data, index){
    //연결 리스트에 노드가 하나도 없는 경우
    if(!this.head) {
        this.head = new Node(data);
        return;
    }

    //사용자가 입력한 index가 연결 리스트의 크기보다 큰 경우, tail 노드로 추가한다.
    if(this.size() < index) {
        this.insertLast(data);
        return;
    }
	
    //사용자가 입력한 index가 0인 경우
    if(index === 0) {
        this.head = new Node(data, this.head);
        return;
    }

    let insert = new Node(data, this.getAt(index));
    this.getAt(index-1).next = insert;
}

//Solution 2
insertAt(data, index) {
    //연결 리스트에 노드가 하나도 없는 경우
    if(!this.head){
        this.head = new Node(data);
        return;
    }

    //사용자가 입력한 index가 0인 경우
    if(index === 0){
        this.head = new Node(data, this.head);
        return;
    }	

    //this.getAt(index - 1)가 존재하지 않는 경우는 사용자가 입력한 index가 연결 리스트의 크기보다 큰 경우 밖에 없다. (그 외 경우는 위의 코드에서 모두 처리했기 때문) 그런 경우는 this.getLast()로 tail 노드를 prev에 할당시켜준다.
    const prev = this.getAt(index - 1) || this.getLast();
    const node = new Node(data, prev.next);
    prev.next = node;
	
}

 

insertLast(data)

//연결 리스트 클래스 내의 다른 메서드를 활용하지 않음
insertLast(data) {
    //노드가 하나도 존재하지 않는 경우
    if(!this.head){
        this.head = new Node(data);
        return;
    } 
	
    //노드가 하나라도 존재하는 경우
    let node = this.head;
    while(node) {
        if(node.next) {
            node = node.next;
        } else {
            node.next = new Node(data);
        }
    }
}

//연결 리스트 클래스 내의 다른 메서드를 활용함
insertLast(data) {
    const last = this.getLast();

    if(last) {
        last.next = new Node(data);
    } else {
        this.head = new Node(data)	
    }
}

반응형

 

검색

getFirst()

getFirst() {
    return this.head;
}

 

getAt(index)

getAt(index) {
    let node = this.head;
	
    if(!node) return null;

    for(let i = 0; i < index; i++) {
        if(node.next) {
            node = node.next;
        } else {
            return null;
        }
    }

    return node;	
}

 

getLast()

getLast() {
    let node = this.head;
    while(node) {
        if(node.next) { 
            node = node.next; 
        } else {
            return node;
        }
    }

    return node;
}

 

삭제

removeFirst()

removeFirst() {
    if(!this.head) return;
    this.head = this.head.next;
}

 

removeAt(index)

removeAt(index) {
    //연결 리스트에 노드가 없는 경우
    if(!this.head) return;
    
    //index가 0, 즉 head 노드인 경우
    if(index === 0) {
        this.head = this.head.next();
        return;
    }
	
    const prev = this.getAt(index -1);
    //사용자의 index가 연결 리스트의 크기보다 큰 경우
    if(!prev || !prev.next) return;
    prev.next = prev.next.next;
}

 

removeLast()

removeLast() {
    //연결 리스트에 노드가 없는 경우
    if(!this.head) {
        return;
    }
	
    //연결 리스트의 노드가 한 개인 경우
    if(!this.head.next) {
        this.head = null; 
        return;
    }

    let prev = this.head;
    let node = this.head.next;

    while(node.next) {
        prev = node; 
        node = node.next;
    }
	
    prev.next = null;
}

 

 

추가 참고 사항

 다른 메서드를 두현 할 필요 없이, insertAt(), getAt(), removeAt() 메서드로 나머지 메서드들을 구현할 수도 있다. 

 

 

 

다음글: [자료구조 with JS] 연결 리스트(Linked List) (3) 반복문과 알고리즘

 

 

 

참고: The Coding Interview Bootcamp: Algorithms + Data Structures (Udemy Course)