[자료구조] 이중 연결 리스트, Add 함수 구현까지

이중연결리스트?

어감에서 알 수 있듯이 이중으로 참조 포인터가 연결되어 있는 노드를 가지는 리스트를 의미한다. 따라서 각 노드들은 값과 함께 이전 노드에 대한 참조와 다음 노드에 대한 참조를 가지며, 이러한 특징으로 인해 정방향과 역방향 모두에서 순회할 수 있다. 이런 점에서 보면 단일 연결리스트에 비해 참조 포인터를 하나 더 가짐으로써 메모리 공간을 더 사용한다는 단점이 있지만, 그것보다 이득이 더 커보이는 것 같다.

 

이중 연결리스트 이전에는..

이중연결 리스트 이전에 단일 연결리스트가 있다. 단일 연결리스트를 구현해보면서 느꼈던 큰 단점은 횡단으로만 이동이 가능하여 검색이나 식제 등의 기능에 있어서 유연성이 많이 부족하다는 점이었다.

 

반면에, 이중 연결리스트의 경우에는 이전 노드에 대한 참조와 다음 노드에 대한 참조를 모두 가지고 있기 때문에, 리스트를 순회할 때 앞 뒤 모두를 확인할 수 있기 때문에, 단일 연결리스트의 고질적인 문제점을 개선할 수 있어보인다.

 

이중 연결리스트에서 노드 클래스를 구현하면

이중 연결리스트는 단일 연결리스트와 달리 참조로 사용되는 포인터가 두 가지 있다. 하나는 이전 노드에 대한 참조, 다른 하나는 다음 노드에 대한 참조를 나타내는 포인터이다.

 

이를 반영해서 Node 클래스를 구현하면 다음처럼 하나의 필드를 추가적으로 가지는 것을 확인할 수 있다.

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

 

이중 연결리스트에서 리스트 클래스를 구현하면

반면 이중 연결리스트에서도 단일 연결리스트와 동일하게 리스트 클래스 자체만 본다면, 동일한 틀을 가진다. 물론 여기서 추가되는 여러 기능을 담당하는 메서드들은 참조 포인터를 하나 더 가지므로 당연히 각 기능에서 사용되는 내부 로직은 차이가 있다.

class List {
 constructor(){
   this.head = null;
   this.length = 0;
 }
}

 

Add 함수 구현하기 | addFirst : 리스트의 젤 앞에 노드 추가

리스트의 젤 앞에 노드를 추가하는 것은 간단하다. 현재 헤드(this.head) 가 null 인 경우에는 새노드(newNode) 를 head 가 되도록 하면되고, 헤드가 존재하는 경우(리스트에 노드가 있는 경우)에는 해당 head의 prev 에 newNode 를 추가하고 참조를 이어주면 된다.

 

addFirst(data){
  const newNode = new Node(data);
  newNode.next = this.head; // 새노드의 다음 노드에 대한 참조는 현재 헤드로 지정(헤드가 비어있으면 null 이 할당)

  if(this.head !== null) {
    this.head.prev = newNode;
  }
  
  this.head = newNode;
  this.length++;
}

 

이렇게 작성하게되면, 새노드의 경우 다음 노드에 대한 참조는 현재 헤드를 가리키게 되며(newNode.next = this.head), 리스트가 비어있는 경우에는 해당 헤드의 자리에 새노드(this.head = newNode)가 들어오게 된다.

 

노드가 존재하는 경우에는 해당 헤드의 이전 노드에 대한 참조를 새노드로 지정하여 참조관계를 생성한다.

 

Add 함수 구현하기 | addLast : 리스트의 끝에 노드 추가하기

리스트의 끝 지점에 노드를 추가하는 경우도 크게 어렵지 않다. 우선 리스트가 비어있는 경우(this.head = == nul)l에는 헤드를 새롭게 추가하는 노드(this.head = newNode)로 설정하고,

 

리스트에 노드가 존재하는 경우(currentNode.next !== null)에는 리스트의 끝지점으로 헤드를 옮기고, 마지막 지점에 도달하였다면 해당 헤드의 다음 노드에 대한 참조를 새노드(currentNode.next = newNode)로 지정한다. 그 후 마지막으로 새노드의 이전 노드에 대한 참조를 현재 헤드로 지정(newNode.prev = currentNode)하면 쉽게 구현할 수 있다.

 

addLast(data){
	const newNode =new Node(data);
    
    if(this.head === null) {
     this.head = newNode;
    } else {
    
   		let currentNode = this.head;
        
        // 리스트의 끝에 도달할 때 까지 순회
        while(currentNode.next !== null) {
           // 헤드를 현재 노드의 다음 노드로 
           currentNode = currentNode.next;
        }
        
        currentNode.next = newNode // 현재 노드의 다음 노드 참조를 새노드로
        newNode.prev = currentNode // 새 노드의 이전 노드 참조를 현재 노드로
    ]
    this.length++;
}

 

 

리스트의 끝 지점에 도달하여 currentNode 와 newNode 사이에 연락처 교환이 이루어지고 있다

 

다음 remove

 

[자료구조] 이중연결리스트 remove 함수(메서드) 만들기