JavaScript 연결 리스트 ( Linked List ), 이중 연결 리스트 ( Double Linked List ), 원형 연결 리스트 ( Circular Linked List )

연결 리스트 : 각 노드가 데이터와 포인터를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

- Head는 연결 리스트의 첫 노드를 가리킨다.

- 노드의 포인터영역은 다음 노드를 가리킨다.

- 연결 리스트의 마지막 노드의 포인터는 Null을 가리킨다.

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

//연결 리스트
function LinkedList(){
    this.head = null;
    this.length = 0;
}

[ 연결리스트 관련 함수 구현 ]

 

🔴 append(data) : 연결리스트 마지막에 data를 값으로 갖는 노드를 추가하는 함수

LinkedList.prototype.append = function(data){
    let newNode = new Node(data);
    if(this.head == null) this.head = newNode; //head가 null이면 ( = 연결리스트에 노드가 없으면 )
    else{
        let thisNode = this.head;
        while(thisNode.next != null){ //thisNode를 마지막 노드까지 옮김
            thisNode = thisNode.next;
        }
        thisNode.next = newNode; //마지막 노드를 가리키는 thisNode의 next가 newNode를 가리키도록 함.
    }
    this.length++; //연결 리스트의 크기 1증가
}

 

🟠 insert(data, position = 0 ) : position에 해당하는 위치에 data를 값으로 갖는 노드를 삽입하는 함수

LinkedList.prototype.insert = function(data, position = 0){
    let newNode = new Node(data);
    if(position > this.length) return false; //입력한 position이 연결리스트의 길이보다 크면 false를 반환
    if(position == 0){ //position이 0이면 새 노드를 맨 앞에 삽입 ( position 미설정시 0 )
        newNode.next = this.head;
        this.head = newNode;
    } else{
        let index = 1;
        let thisNode = this.head; //thisNode는 newNode의 앞 노드가 됨
        while(index != position){ //position에 해당하는 앞 노드까지 thisNode 이동
            thisNode = thisNode.next;
            index++;
        }
        newNode.next = thisNode.next; //newNode의 next는 thisNode의 next를 넘겨받음
        thisNode.next = newNode; //thisNode의 next를 newNode로 지정함으로써 thisNode의 다음 노드는 newNode가 됨.
    }
    this.length++; //연결리스트의 길이 1 증가
}

 

🟡remove(val) : 연결리스트에서 val을 값으로 하는 첫번째 노드를 찾아 삭제하는 함수

LinkedList.prototype.remove = function(val) {
    let thisNode = this.head;
    let prev; //삭제하는 노드의 앞 노드를 가리킬 변수
    if(this.head.data == val){ //첫 노드의 값이 val이면 head를 다음 노드로 가리킴
        this.head = this.head.next;
    } else{
        while(thisNode.data != val){ //thisNode의 값이 val이 될 때까지 thisNode를 다음 노드로 이동시키며, prev는 그 전 노드를 가리킴
            prev = thisNode; 
            thisNode = thisNode.next;
            if(thisNode == null) return false; //끝까지 갔는데 val값을 가지는 노드가 없으면 false 리턴
        }   
        prev.next = thisNode.next; //삭제할 노드의 이전 노드의 next값을 thisNode의 next로 저장하면서 thisNode를 연결리스트에서 제거
    }
    this.length--; //연결리스트의 길이 1 감소
}

 

🟢removeAt(position = 0) : 연결리스트에서 position 위치에 해당하는 노드 제거

LinkedList.prototype.removeAt = function(position = 0){
    if(position >= this.length) return false;//제거하고자 하는 노드의 위치가 연결리스트의 길이보다 크면 false반환
    if(position == 0){ //position이 0이면 this.head를 다음 노드로 옮겨 첫 노드 제거
        this.head = this.head.next;
    } else{
        let thisNode = this.head.next;
        let prev = this.head;
        let index = 1;
        while(index != position){ //thisNode가 제거할 노드를 가리킬 때 까지 이동 ( prev는 그 전 노드를 가리키도록 함 )
            prev = thisNode;
            thisNode = thisNode.next;
            index++;
        }
        prev.next = thisNode.next; //prev의 next를 thisNode의 next를 가리키게 함으로써 thisNode를 연결리스트에서 제거
    }
    this.length--; //연결리스트의 길이 1 감소
}

 

---

이중 연결 리스트 : 각 노드가 데이터와 포인터를 가지며, 두 줄로 연결되어 있는 방식으로 데이터를 저장하는 구조

- 각 노드는 이전노드를 가리키는 포인터와 다음 노드를 가리키는 포인터를 가진다 ( 2개의 포인터 )

- 이중 연결리스트의 첫 노드는 head가, 마지막 노드는 tail이 가리킨다. 

- 이중 연결리스트의 첫 노드의 prev 포인터와 마지막 노드의 next포인터는 null을 가리킨다. 

//노드
function Node(data){ 
    this.data = data;
    this.next = null;
    this.prev = null;
}

//이중 연결 리스트
function DoubleLinkedList(){
    this.head = null;
    this.tail = null;
    this.length = 0;
}

[ 이중 연결리스트 관련 함수 구현 ]

 

🔴 append(data) : 이중 연결리스트 마지막에 data를 값으로 갖는 노드를 추가하는 함수

DoubleLinkedList.prototype.append = function(data){
    let newNode = new Node(data);
    if(this.head == null) { //이중 연결리스트에 노드가 없으면 head와 tail을 newNode로 설정
        this.head = newNode;
        this.tail = newNode;
    } else{
        let thisNode = this.tail; //thisNode를 끝 노드로 지정
        thisNode.next = newNode; //끝 노드의 next는 newNode
        newNode.prev = thisNode; //newNode의 prev는 thisNode
        this.tail = newNode; //이중 연결리스트이 tail을 newNode로 설정
    }
    this.length++; //이중연결리스트 길이 1 증가
}

 

🟠 insert(data, position = 0 ) : position에 해당하는 위치에 data를 값으로 갖는 노드를 삽입하는 함수

DoubleLinkedList.prototype.insert = function(data, position = 0){
    let newNode = new Node(data);
    if(position > this.length) return false;
    if(this.head == null){ //이중 연결 리스트가 비어있으면 head와 tail을 newNode로 지정
        this.head = newNode;
        this.tail = newNode;
    } else if(position == 0){ //position이 0이면 첫 노드로 newNode를 삽입
        this.head.prev = newNode; //기존 첫 노드의 prev를 newNode로
        newNode.next = this.head; //newNode의 next를 기존의 head로
        this.head = newNode; //head를 newNode로 지정
    } else{
    	if(position == this.length-1){ //position 이 마지막이라면 tail을 이용하여 마지막에 노드 삽입
        	newNode.prev = this.tail; 
            this.tail.next = newNode;
            this.tail = newNode;
        } else {
        	let index = 1;
        	let thisNode = this.head; //newNode의 앞 노드가 될 노드
        	while(index != position){ //thisNode가 position의 앞 노드를 가리킬 때까지 이동
            	thisNode = thisNode.next;
            	index++;
        	}
        	thisNode.next.prev = newNode; //삽입 위치 다음 노드의 prev는 newNode를 가리킴
        	newNode.next = thisNode.next; //newNode의 next는 thisNode.next를 가리킴 ( 기존 노드의 다음 노드 )
        	newNode.prev = thisNode; //newNode의 prev는 thisNode를 가리킴
        	thisNode.next = newNode; //thisNode의 next는 newNode를 가리킴
    	}
    }
    this.length++; //이중 연결리스트의 길이 1 증가
}

 

🟡remove(val) : 이중 연결리스트에서 val을 값으로 하는 첫번째 노드를 찾아 삭제하는 함수

DoubleLinkedList.prototype.remove = function(val) {
    let thisNode = this.head;
    let prev;
    if(this.head.data == val){ //첫 번째 노드가 삭제할 노드이면
        this.head = this.head.next; //head를 다음 노드로 지정
        this.head.prev = null; //다음 노드의 prev를 null로 지정
    } else{
        while(thisNode.data != val){ //val을 값으로 가지는 노드를 찾을 때 까지 thisNode이동
            prev = thisNode;
            thisNode = thisNode.next;
            if(thisNode == null) return false;
        }
        if(thisNode == this.tail){ //마지막 노드가 val을 값으로 가지면
            prev.next = null; //이전 노드의 next를 null로 지정
            this.tail = prev; //tail가 이전 노드를 가리키도록 함.
        } else{ //삭제할 노드(thisNode)가 시작노드도, 마지막 노드도 아니라면
            prev.next = thisNode.next; //이전 노드의 next는 thisNode의 next로
            thisNode.next.prev = prev; //삭제할 다음 노드의 prev는 이전 노드로 설정
        }
    }
    this.length--; //이중 연결 리스트의 길이 1 감소
}

 

🟢removeAt(position = 0) : 연결리스트에서 position 위치에 해당하는 노드 제거

DoubleLinkedList.prototype.removeAt = function(position = 0){
    if(position >= this.length) return false;
    if(position == 0){ //삭제할 노드가 첫 노드라면
        this.head.next.prev = null; //삭제할 노드의 다음 노드의 prev를 null로 설정
        this.head = this.head.next; //head를 다음 노드로 설정
    } else if(position == this.length-1){ //삭제할 노드가 마지막 노드라면
        this.tail.prev.next = null; //전 노드의 next를 null로 설정
        this.tail = this.tail.prev; //tail을 전 노드로 설정
    } else{ //삭제할 노드가 첫 노드도, 마지막 노드도 아니라면
        let thisNode = this.head.next;
        let prev = this.head;
        let index = 1;
        while(index != position){ //thisNode가 삭제할 노드를 가리킬 때 까지 이동, prev는 그 전 노드를 가리킴
            prev = thisNode;
            thisNode = thisNode.next;
            index++;
        }
        prev.next = thisNode.next; //prev의 next는 thisNode의 next를 가리킴
        thisNode.next.prev = prev; //삭제할 노드의 다음노드의 prev는 prev를 가리킴
    }
    this.length--;
}

---

원형 연결 리스트 : 각 노드가 데이터와 포인터를 가지며, 원형 형태로 연결되어 있는 방식으로 데이터를 저장하는 구조

- 원형 연결 리스트에서 마지막 노드의 포인터는 첫 노드( head )를 가리킨다.

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

//원형 연결 리스트
function CircularLinkedList(){
    this.head = null;
    this.length = 0;
}

[ 원형 연결리스트 관련 함수 구현 ]

🔴 append(data) : 원형 연결리스트 마지막에 data를 값으로 갖는 노드를 추가하는 함수

CircularLinkedList.prototype.append = function(data){
    let newNode = new Node(data);
    if(this.head == null) { //원형 연결리스트가 비어있다면
        this.head = newNode; //head가 newNode를 가리키도록 함
        newNode.next = newNode; //newNode의 next가 자기자신을 가리키도록 함.
    } else{
        let thisNode = this.head; 
        while(thisNode.next != this.head){ //thisNode의 next가 head를 가리킬 때 까지(마지막 노드를 가리킬 때까지) 이동
            thisNode = thisNode.next;
        }
        thisNode.next = newNode; //마지막 노드의 next가 newNode를 가리키도록 함
        newNode.next = this.head; //newNode의 next가 첫 노드를 가리키도록 함.
    }
    this.length++; //원형 연결리스트의 길이 1 증가
}

 

🟠 insert(data, position = 0 ) : position에 해당하는 위치에 data를 값으로 갖는 노드를 삽입하는 함수

CircularLinkedList.prototype.insert = function(data, position = 0){
    let newNode = new Node(data);
    if(position > this.length) return false;
    if(this.head == null){
        this.head = newNode;
        newNode.next = newNode;
    } else if(position == 0){ //position이 0일 때 ( 원형연결리스트의 처음에 노드를 삽입할 때 )
        let thisNode = this.head;
        while(thisNode.next != this.head){ //thisNode가 마지막 노드를 가리킬 때까지 이동
            thisNode = thisNode.next;
        }
        thisNode.next = newNode; //마지막 노드(thisNode)의 next가 newNode(첫노드)를 가리키도록 함.
        newNode.next = this.head;
        this.head = newNode;
    } else{
        let index = 1;
        let thisNode = this.head;
        while(index != position){
            thisNode = thisNode.next;
            index++;
        }
        newNode.next = thisNode.next;
        thisNode.next = newNode;        
    }
    this.length++;
}

 

🟡remove(val) : 이중 연결리스트에서 val을 값으로 하는 첫번째 노드를 찾아 삭제하는 함수

CircularLinkedList.prototype.remove = function(val) {
    let thisNode = this.head;
    let prev;
    if(this.head.data == val){ //삭제되는 노드가 첫 노드라면
        while(thisNode.next != this.head){ 
            thisNode = thisNode.next;
        }
        thisNode.next = this.head.next; //thisNode가 마지막 노드를 가리키게 한 후 thisNode의 next를 첫 노드의 다음노드를 가리키도록 함.
        this.head = this.head.next;
    } else{
        while(thisNode.data != val){
            prev = thisNode;
            thisNode = thisNode.next;
            if(thisNode == null) return false;
        }
        prev.next = thisNode.next;
    }
    this.length--;
}

 

🟢removeAt(position = 0) : 연결리스트에서 position 위치에 해당하는 노드 제거

CircularLinkedList.prototype.removeAt = function(position = 0){
    if(position >= this.length) return false;
    if(position == 0){
        let thisNode = this.head;
        while(thisNode.next != this.head){
            thisNode = thisNode.next;
        }
        thisNode.next = this.head.next;
    } else{
        let thisNode = this.head.next;
        let prev = this.head;
        let index = 1;
        while(index != position){
            prev = thisNode;
            thisNode = thisNode.next;
            index++;
        }
        prev.next = thisNode.next;
    }
    this.length--;
}