[ 선형 자료구조 ] 연결 리스트 - Doubly Linked List(이중 연결 리스트)

Computer Science/자료 구조 2023. 1. 3. 16:47

연결 리스트는 각각의 요소들이 "노드"에 저장되는 선형 자료 구조이다. 각 노드들은 다음 노드에 대한 참조값을 가지며 이를 "링크"라 한다. 이러한 노드들로 이루어진 연결 리스트는 노드의 link filed를 사용함으로써 데이터의 추가 및 삭제를 모든 리스트 인덱스에 대한 방문 및 재구성 없이 실행 가능하다.

연결 리스트는 스택, 큐, 그래프 등을 구현하는데 자주 사용되며, 그 종류로는 Singly linked list, Doubly linked list 등이 있다.

1. 기본 배경 지식

1) Node

연결 리스트를 구성하는 노드는 Data filed, Linke filed 두 가지 필드로 이루어진 묶음이다.

Data filed는 node는 integer, character 등 노드가 보유할 실제 데이터를 저장하는 필드이고
Link filed는 다음 노드에 대한 참조값을 보유하는 필드이며 마지막 노드에선 'null'을 갖는다. (singly linked list의 경우 다음 노드에 대한 참조값만 저장하고, doubly linked list의 경우 이전 노드에 대한 참조값을 추가적으로 보유한다.)
연결 리스트의 가장 첫번째 노드를 head라 하고 마지막 노드를 tail이라 한다.

Doubly linked list의 node 예시)

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

2. Doubly Linked List

1) 기본 구조

doubly linked list에서 노드 시퀀스로 구성된 데이터 구조이다. 각 노드는 시퀀스 상의 다음 노드에 대한 참조값 뿐만 아니라 이전 노드에 대한 참조값 역시 linke filed에 하며, 따라서 양방향으로 연결리스트에 대한 횡단이 가능하다.

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

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

2) Doubly Linked List methods

(1) Push

연결 리스트의 마지막에 노드를 추가

기존 tail의 next를 newNode로 변경
newNode의 prev를 tail로 초기화
tail을 newNode로 변경
length 증가

push(value) {
    let newNode = new Node(value);
    
    if (this.tail === null) { // 리스트가 비었을 경우
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;  // 기존 tail의 next를 newNode에 대한 참조값으로 갱신
      newNode.prev = this.tail;  // newNode의 prev를 기존 tail 노드에대한 참조값으로 설정
      this.tail = newNode;       // tail을 newNode로 갱신
    }
    
    this.length++;
    
    return;
}

(2) pop

연결 리스트의 마지막 노드를 삭제 후 해당 노드 반환

tail을 tail 이전의 노드로 변경
tail의 next를 null로 변경
리스트의 length를 감소

pop() {
    if (this.tail === null) return undefined // 빈 리스트인 경우

    let removedNode = this.tail;

    if (this.head === this.tail) { // 길이가 1인 리스트인 경우(한개의 노드인 경우)
        this.head = null;
        this.tail = null;
    } else {                      // 리스트의 노드가 2개 이상인 경우
        this.tail = this.tail.prev; // tail을 기존 tail의 노드의 prev가 가리키고 있는 노드로 갱신
        this.tail.next = null;      // 갱신된 tail의 next를 null로 갱신
    }

    this.length--;  // length 감소

    return removedNode
}

(3) shift

shilft는 리스트의 가정 첫번째 요소를 지우고 해당 데이터를 반환

head를 기존 head의 next 노드로 변경
head의 prev를 null로 초기화
리스트의 length 프로퍼티를 감소시킨다.

shift() {
    if (this.head === null) return undefined; // 리스트가 노드를 갖지 않을 경우

    let removedNode = this.head; // 실행 후 반환할 값 저장
    
	if (this.head === this.tail) { // 리스트의 길이가 1인 경우
      this.head = null;
      this.tail = null;
    } else { // 리스트의 길이가 2 이상인 경우
      this.head = this.head.next;
      this.head.prev = null;
    }
    
    this.length--;  // length 갱신

    return removedNode;  // 기존 첫번째 노드 반환
  }

(4) unshift

연결리스트의 시작 부분에 새로운 노드를 추가

삽입될 노드의 next를 head 노드로 변경
삽입될 노드의 prev를 null로 변경
head 노드의 prev를 삽입될 노드로 변경
head를 신규 노드로 변경
length 증가

unshift(value) {
    let newNode = new Node(value);  // 추가할 값을 가진 노드 생성
    
    if (this.tail != null) { // 빈 리스트가 아닌 경우
    	newNode.next = this.head; // 추가할 노드의 next, prev값 초기화
    	this.head.prev = newNode; // 기존 head 노드의 prev를 새롭게 추가할 노드로 변경
    } else { // 빈 리스트인 경우
    	newNode.next = null; // 추가할 노드의 next, prev값 초기화
    	this.tail = newNode; // tail 갱신
    }
    
    this.head = newNode; // head 갱신
    this.length++; // length 증가
    
    return;
}

(5) get

주어진 인덱스의 노드가 가지고 있는 데이터를 반환

head에서부터 idx까지 순회
idx의 노드가 가진 값 반환

get(index) {
    if (index < 0 || index >= this.length) return undefined; // 잘못된 인덱스가 주어졌을 경우 undefined 반환

    let current = this.head;  // 현재 노드를 나타낼 current 선언 후 head저장(head부터 시작)
    
    for (let i = 0; i < index; i++) {
      current = current.next;  // 순회를 통해 current를 idx번째 노드까지 갱신
    }

    return current;  // idx번째 노드 반환
  }

(6) set

주어진 인덱스의 값을 갱신 및 설정

head부터 idx 노드까지 순회
idx의 노드가 가지는 값 갱신

set(index, value) {
    if (index < 0 || index >= this.length) return undefined;  // 잘못된 인덱스가 주어졌을 시 undefined 반환

    let current = this.head;  // 현재 노드를 저장할 current 선언
    
    for (let i = 0; i < index; i++) {
      current = current.next;  // 주어진 인덱스까지 current 갱신
    }

    current.value = value;  // 주어진 인덱스의 노드의 value 값 갱신
  }

(7) insert

주어진 인덱스에 새로운 노드를 추가

삽입될 노드의 prev, next를 인덱스 이전 노드, 인덱스 노드로 변경
인덱스의 이전 노드의 next를 새로 삽입할 노드로 변경한다.
인덱스 노드의 prev를 새로 삽입할 노드로 변경한다.
length를 증가시킨다.

insert(index, value) {
    if (index < 0 || index > this.length) return undefined; // 잘못된 인덱스가 주어졌을 시 undefined 반환
    if (index === 0) return this.unshift(value)        // 첫 번째에 추가하는 경우
    if (index === this.length) return this.push(value) // 마지막에 추가하는 경우
    
    let newNode = new Node(value); // 추가할 노드 생성 후 변수 newNode에 할당
    let prev = this.get(index - 1); // prev 변수에 이전 노드 저장
    let next = prev.next; // next 변수에 인덱스의 노드 저장
	
    newNode.prev = prev; 
    newNode.next = next;  // 주어진 인덱스에 추가할 노드의 next, prev 초기화
    
    prev.next = newNode; // 이전 노드의 next를 newNode로 변경
    next.prev = newNode // 주어진 인덱스에 자리잡고 있던 노드(밀려나게 된 노드)의 prev를 newNode로 변경
    
    this.length++;
    
    return
  }

(8) remove

주어진 인덱스의 노드 삭제

인덱스 이전 노드의 next를 인덱스 다음 노드로 변경
인덱스 다음 노드의 prev를 인덱스 이전 노드로 변경
length 갱신

remove(index){
        if(index < 0 || index >= this.length) return null; // 인덱스의 범위가 잘못된 경우 null 반환
        if(index === 0) return this.shift();               // 첫 노드를 지울 경우 shift()
        if(index === this.length - 1) return this.pop();   // 마지막 노드를 지울 경우 pop()
        
        let prev = this.get(index - 1);  // 인덱스 이전 노드
        let next = prev.next.next;  // 인덱스 이후 노드             
                                                     
        prev.next = next; // 인덱스 이전 노드의 next 변경
        next.prev = prev; // 인덱스 이후 노드의 prev 변경
        
        this.length--;    // length 프로퍼티 갱신
        
        return        
 }

(9) reverse

리스트를 뒤집는다.

reverse() {
    if (this.length <= 1) return;

    let current = this.head;
    let temp = null;
    
    while (current != null) { // 모든 노드의 next, prev 교환
      temp = current.prev;
      current.prev = current.next;
      current.next = temp;
      current = current.prev;
    }

    this.tail = this.head;
    this.head = temp.prev;
	
    return
  }

(10) 정리

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

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

  print() {
    let current = this.head;
    let arr = [];

    for (let i = 0; i < this.length; i++) {
      arr.push(current.value)
      current = current.next; 
    }

    return arr
  }

  push(value) {
    let newNode = new Node(value);

    if (this.tail === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode; 
      newNode.prev = this.tail; 
      this.tail = newNode; 
    }

    this.length++;

    return;
  }

  pop() {
    if (this.tail === null) return undefined; 

    let removedNode = this.tail;

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

    this.length--;

    return removedNode;
  }

  shift() {
    if (this.head === null) return undefined;

    let removedNode = this.head; 

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

    this.length--;

    return removedNode; 
  }

  unshift(value) {
    let newNode = new Node(value); 

    if (this.tail != null) {
      newNode.next = this.head; 
      this.head.prev = newNode; 
    } else {
      newNode.next = null; 
      this.tail = newNode; 
    }

    this.head = newNode; 
    this.length++; 

    return;
  }

  get(index) {
    if (index < 0 || index >= this.length) return undefined;

    let current = this.head; 

    for (let i = 0; i < index; i++) {
      current = current.next; 
    }

    return current; 
  }

  set(index, value) {
    if (index < 0 || index >= this.length) return undefined; 

    let current = this.head; 

    for (let i = 0; i < index; i++) {
      current = current.next;
    }

    current.value = value;
  }

  insert(index, value) {
    if (index < 0 || index > this.length) return undefined;
    if (index === 0) return this.unshift(value);
    if (index === this.length) return this.push(value); 

    let newNode = new Node(value); 
    let prev = this.get(index - 1); 
    let next = prev.next; 

    newNode.prev = prev;
    newNode.next = next; 

    prev.next = newNode; 
    next.prev = newNode;

    this.length++;

    return;
  }

  remove(index) {
    if (index < 0 || index >= this.length) return null; 
    if (index === 0) return this.shift(); 
    if (index === this.length - 1) return this.pop(); 

    let prev = this.get(index - 1); 
    let next = prev.next.next;

    prev.next = next;
    next.prev = prev; 

    this.length--; 

    return;
  }

  reverse() {
    if (this.length <= 1) return;

    let current = this.head;
    let temp = null;

    while (current != null) {
      temp = current.prev;
      current.prev = current.next;
      current.next = temp;
      current = current.prev;
    }

    this.tail = this.head;
    this.head = temp.prev;

    return;
  }
}

3. Linked LIst / Array List 장단점 비교

	Array List	Singly Linked LIst	Doubly Linked List
pros	1. 인덱스에 대한 접근 속도가 빠르고 일정 2. 리스트 끝에서의 빠른 삽입 및 삭제 3. 연속된 메모리 형태로 특정 연산에서의 이점을 가짐	1. 빠른 삽입과 삭제 2. 연속된 메모리를 차지하지 않으므로 메모리 할당에 대한 제약이 적다.	1. 빠른 삽입과 삭제 2. 연속된 메모리를 차지하지 않으므로 메모리 할당에 대한 제약이 적다. 3. 양방향으로 횡단 가능
cons	1. 리스트의 첫부분 및 중간에서의 삽입 및 삭제가 느림(해당 인덱스 이후의 모든 원소의 이동이 필요) 2. 리스트 크기의 변화가 빈번할 경우 공간을 낭비할 우려가 큼 3. 연속된 메모리를 차지하므로 배열의 크기에 따라 메모리 할당이 어려울 수 있다.	1. 각 원소에 대한 접근 속도가 느림 (링크에 따른 횡단 필요) 2. 배열 리스트에 비해 복잡하다.	1. 각 원소에 대한 접근 속도가 느림 (링크에 따른 횡단 필요) 2. 각 노드가 이전 노드에 대한 참조도 저장하므로 singly linked list보다 많은 메모리 필요 3. 배열 리스트에 비해 복잡하다.

	Circular Singly Linked List	Circular Doubly Linked List
pros	1. 빠른 삽입과 삭제 2. 연속된 메모리를 차지하지 않으므로 메모리 할당에 대한 제약이 적다. 3. 무한정으로 횡단 가능	1. 빠른 삽입과 삭제 2. 연속된 메모리를 차지하지 않으므로 메모리 할당에 대한 제약이 적다. 3. 양방향으로 무한정 횡단 가능
cons	1. 각 원소에 대한 접근 속도가 느림 (링크에 따른 횡단 필요) 2. 단순 연결 리스트에 비해 복잡하다. 3. 무한루프에 빠질 가능성이 있다.	1. 각 원소에 대한 접근 속도가 느림 (링크에 따른 횡단 필요) 2. 각 노드가 이전 노드에 대한 참조도 저장하므로 circular singly linked list보다 많은 메모리 필요 3. 단순 연결 리스트에 비해 복잡하다. 3. 무한루프에 빠질 가능성이 있다.

4. Linked List / Array List 시간 복잡도

	Array List	Singly Linked List	Doubly Linked List	Circular Linked List
insertion at the beginning	O(n)	O(1)	O(1)	O(1)
insertion at the end	O(1)	O(n)	O(1)	O(1)
insertion in the middle	O(n)	O(n)	O(1)	O(1)
deletion at the beginning	O(n)	O(1)	O(1)	O(1)
deletion at the end	O(1)	O(n)	O(1)	O(1)
deletion in the middle	O(n)	O(n)	O(1)	O(1)
Search	O(n)	O(n)	O(n)	O(n)
Accese	O(1)	O(n)	O(n)	O(n)

'Computer Science > 자료 구조' 카테고리의 다른 글

[ 선형 자료구조 ] 배열 & 리스트 (0)	2023.01.06
[ 선형 자료구조 ] 연결 리스트 - Circular Linked List(원형 연결 리스트) (0)	2023.01.04
[ 선형 자료구조 ] 연결 리스트 - Singly linked list(단순 연결 리스트) (0)	2022.12.28
[ 복잡도 ] 정렬 알고리즘의 복잡도 (0)	2022.12.26
[ 복잡도 ] 시간 복잡도와 공간 복잡도 (0)	2022.12.26

ABOUT ME

COMPMOS COMPMOS

1. 기본 배경 지식

1) Node

2. Doubly Linked List

1) 기본 구조

2) Doubly Linked List methods

(1) Push

(2) pop

(3) shift

(4) unshift

(5) get

(6) set

(7) insert

(8) remove

(9) reverse

(10) 정리

3. Linked LIst / Array List 장단점 비교

4. Linked List / Array List 시간 복잡도

'Computer Science > 자료 구조' 카테고리의 다른 글

티스토리툴바

ABOUT ME

1. 기본 배경 지식

1) Node

2. Doubly Linked List

1) 기본 구조

2) Doubly Linked List methods

(1) Push

(2) pop

(3) shift

(4) unshift

(5) get

(6) set

(7) insert

(8) remove

(9) reverse

(10) 정리

3. Linked LIst / Array List 장단점 비교

4. Linked List / Array List 시간 복잡도

'Computer Science > 자료 구조' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바