[ 선형 자료구조 ] 연결 리스트 - Singly linked list(단순 연결 리스트)

Computer Science/자료 구조 2022. 12. 28. 19:17

연결 리스트는 각각의 요소들이 "노드"에 저장되는 선형 자료 구조이다. 각 노드들은 다음 노드에 대한 참조값을 가지며 이를 "링크"라 한다. 이러한 노드들로 이루어진 연결 리스트는 노드의 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이라 한다.

Singly linked list의 node 예시)

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

2. Singly Linked List

1) 기본 구조

singly linked list에서는 각 노드는 data filed에 data를 저장하고 link filed에 다음 노드에 대한 참조값을 저장한다. 연결리스트에 대한 횡단은 한방향으로만 이루어진다.

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

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

2) Singly Linked List methods

(1) Push

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

tail의 next를 newNode로 변경한다.
newNode를 tail로 설정한다.
length를 증가시킨다.

push(value) {
    const newNode = new Node(value); // push할 값을 가지는 노드 생성

    if (this.head === null) {        // 노드의 원소가 없는 경우
      this.head = newNode;
      this.tail = newNode;           // 추가된 노드가 head, tail 둘다 됨
    } else {                         // 그 외의 경우
      this.tail.next = newNode;      // 기존 tail의 노드의 next를 갱신하고
      this.tail = newNode;           // tail값 갱신
    }

    this.length++;                   // 리스트의 length 증가
    
    return
}

(2) pop

pop 메소드는 연결 리스트의 마지막 노드를 삭제

tail 노드 바로 이전 노드의 next를 null로 변경한다.
tail 값을 tail 노드의 바로 이전 노드로 갱신한다.
length를 감소시킨다.

pop() {
    if (this.head === null) return undefined; // 빈 리스트일 경우 undefined를 반환한다.

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

    if (this.length === 1) { // 리스트의 길이가 1인 경우
      this.head = null;
      this.tail = null; 
    } else {                // 리스트의 길이가 2 이상인 경우
      while (current.next !== null) { // current가 tail이 될 때까지 반복
        previous = current;
        current = current.next; 
      }
      
      previous.next = null; 
      this.tail = previous; 
    }

    this.length--;
    
    return current
 }

(3) shift

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

head를 기존 head의 next가 가리킨 노드로 갱신한다.
리스트의 length 프로퍼티를 감소시킨다.

shift() {
    if (this.head === null) return undefined; // 빈 리스트의 경우

    let removedNode = this.head; // 실행 후 반환할 노드 저장
    this.head = this.head.next;  // head 갱신
    this.length--;               //length 갱신

    if (this.head === null) this.tail = null; // 리스트의 길이가 1일 경우 tail 값 또한 갱신

    return removedNode;  // 지워진 노드 반환
  }

(4) unshift

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

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

unshift(value) {
    let newNode = new Node(value);  // 추가할 값을 가진 노드 생성
    
    if (this.tail === null) {
        this.tail = newNode;
        this.head = newNode;
		this.length++

        return
    } // 빈 리스트의 경우
    
    newNode.next = this.head; // 앞서 생성한 노드의 next값 설정
    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

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

삽입될 노드의 next를 목표 인덱스 이전 노드의 next로 초기화
목표 인덱스 이전 노드의 next를 삽입될 노드로 변경

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);
    let prev = this.get(index - 1);
    
    newNode.next = prev.next;
    prev.next = newNode; 

    this.length++;
    
    return
  }

(8) remove

주어진 인덱스의 노드 삭제

head부터 주어진 인덱스의 노드까지 순회하며 주어진 인덱스 및 바로 이전 인덱스의 노드에 접근
바로 이전 노드의 next를 주어진 인덱스 이후의 노드에 대한 참조값으로 갱신
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 removedNode = prev.next;          // 전의 노드를 prev에 저장 후 next를
                                     // 인덱스 바로 후의 노드로 변경
    prev.next = removedNode.next;
    this.length--; // length 프로퍼티 갱신

    return        
 }

(9) reverse

리스트를 뒤집는다.

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

    let current = this.head;
    let previous = null;
    let next = null;

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

    this.tail = this.head;
    this.head = previous;
  }

(10) 정리

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

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

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

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

    this.length++;

    return;
  }

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

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

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      while (current.next !== null) {
        previous = current;
        current = current.next;
      }

      previous.next = null;
      this.tail = previous;
    }

    this.length--;

    return current;
  }

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

    let removedNode = this.head;
    this.head = this.head.next;
    this.length--; //length 갱신

    if (this.head === null) this.tail = null; 

    return removedNode;
  }

  unshift(value) {
    let newNode = new Node(value);
    
    if (this.tail === null) {
      this.tail = newNode;
      this.head = newNode;
      this.length++;
      return;
    } 

    newNode.next = this.head; 
    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);

    newNode.next = prev.next;
    prev.next = 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 removedNode = prev.next; 

    prev.next = removedNode.next;
    this.length--;

    return;
  }

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

    let current = this.head;
    let previous = null;
    let next = null;

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

    this.tail = this.head;
    this.head = previous;
  }
}

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
[ 선형 자료구조 ] 연결 리스트 - Doubly Linked List(이중 연결 리스트) (0)	2023.01.03
[ 복잡도 ] 정렬 알고리즘의 복잡도 (0)	2022.12.26
[ 복잡도 ] 시간 복잡도와 공간 복잡도 (0)	2022.12.26

ABOUT ME

COMPMOS COMPMOS

1. 기본 배경 지식

1) Node

2. Singly Linked List

1) 기본 구조

2) Singly Linked List methods

(1) Push

(2) pop

(3) shift

(4) unshift

(5) get

(6) set

(7) insert

(8) remove

(9) reverse

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

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

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

티스토리툴바

ABOUT ME

1. 기본 배경 지식

1) Node

2. Singly Linked List

1) 기본 구조

2) Singly Linked List methods

(1) Push

(2) pop

(3) shift

(4) unshift

(5) get

(6) set

(7) insert

(8) remove

(9) reverse

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

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

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

관련글 관련글 더보기

티스토리툴바