[자료구조] 단일 연결 리스트 | Add 구현하기(2). sub | 뒤로 노드 추가하기

 

[ 자료구조] 단일 연결 리스트 - Add 구현하기[1]. sub | 노드를 앞으로 추가하기

 

이전 시간에는 단일 연결 리스트에 노드를 추가하는 방법 중 노드를 앞으로 추가하는 함수에 대해서 정리해 보았는데, 오늘은 그 반대이자 일반적인 방식인 노드를 뒤로 추가하는 방식에 대해 정리하고자 한다.

 

 노드를 뒤로 추가하는 add 함수

노드를 앞으로 추가하는 방법은 앞에서 알아 봤듯이 새로운 노드가 이전 노드를 참조하게 하는 방식으로 꼬리에 꼬리를 물도록 설계하는 것 이었다.

  add(data) {
    const newNode = new Node(data) // 새로운 노드를 생성한다.
    
    newNode.next = this.head // 추가된 노드의 다음 노드는 현재 노드를 참조
    this.head = newNode // 현재 노드를 참조하는 head 에 새로운 노드를 할당
    this.size++ // 새로운 노드가 추가되었으므로 리스트의 크기를 증가시킨다.
 }

 

 

그럼 노드를 뒤로 추가하려면 어떻게 하면 될까? 당연히 노드가 참조하는 방향을 반대로 돌리면 될 뿐이다.

 

일단, 이를 구현한 코드와 과정은 다음과 같다.

 appendEnd(data){
        const newNode = new Node(data) // newNode =  { data : 1, next : null }
        
     	// 리스트가 텅 비어있었던 경우에는 새노드를 즉시 헤드로 지정하고 함수를 종료한다.
         if ( this.head === null) return this.head = newNode
             
        // 리스트가 노드가 존재한다면, 마지막 노드의 다음 참조가 null이 될 때 까지 헤드를 옮긴다.
         let current = this.head;
         while ( current.next !== null ) {
                current = current.next   
            }                    
        // 마지막 노드의 다음 참조를 새로운 노드로 지정해서 꼬리를 만든다.
        // 예를들어, 5 다음에 추가된게 2라면 5-> 2 와 같이 꼬리를 달아서 포장해준다.
         current.next  = newNode 
         this.size++
    }

 

 

해당 로직에서 제일 중요한 원리는 기존 노드의 다음 노드에 대한 참조를 새롭게 추가되는 노드로 지정하는 것이다. 그래야 5 -> 4 -> 3 과 같이 꼬리에 꼬리를 무는 연결 리스트를 만들 수 있기 때문이다.

 

결과적으로 이전 노드가 다음 노드를 화살표로 연결하는 듯 한 그림을 다음과 같이 확인할 수 있다면, 정상적으로 로직이 구현된 것이다.

 

 

시간복잡도와 공간복잡도

단일 연결리스트에서 노드를 뒤로 추가하는 것은 마지막 노드의 다음 노드에 대한 참조인 꼬리를 이어주기만 하면 되는 작업이기 때문에 노드를 추가하는 작업은 상수 시간복잡도로 O(1) 이 된다.

 

공간복잡도의 경우도 마찬가지로 O(1) 이다. 추가되는 노드들은 참조로 서로 이어지는 각각의 독립된 메모리 공간을 가지기 때문에, 아무리 노드의 수가 증가하더라도 별도의 메모리 공간을 가지므로 상수시간복잡도를 가진다.

 

반면 배열의 경우에는 데이터의 길이 만큼 메모리 공간을 연속적으로 확장시켜나가기 때문에 선형시간복잡도인 O(n)이 된다는 점을 참고하면 좋다.

 

 

 

 

<다음 포스트>

[자료구조] 단일 연결 리스트 | search 구현하기.sub | Index 를 사용하여 노드 찾기