Linked List (연결 리스트)

* 이 글은 제로초님의 강의 '비전공자의 전공자 따라잡기 - 자료구조(with JavaScript)' 를 듣고 정리하였습니다.

출처 : https://www.zerocho.com/category/Algorithm/post/58008a628475ed00152d6c4d  

 

목차

 

연결리스트란?

연결 리스트는 배열과 다르다.
(자바스크립트에서 배열이 없다고 생각한 후에 연결리스트 개념을 공부해보자)
배열처럼 메모리상에 index에 의한 물리적 배치를 하지 않고, node를 생성 후 해당 node의 pointer에 의해 다음 node를 연결한다. 즉, 여러 node들이 연결되어있는 선형적 데이터 구조다.
이를 통해 연결 리스트는 데이터 삽입/삭제시 데이터의 구조를 재정렬하지 않아도 된다.

💡노드(node)란?
연결리스트의 각 요소들은 node라고 말한다. node는 일반적으로 data 그리고 다음 node를 가리키는 link, 이 2가지로 구성되고 데이터의 유형은 2가지 뿐만 아니라 다양하게 올 수 있다. node는 link를 통해 다음 node에 접근할 수 있으며, node들은 다음에 올 node의 정보를 갖고 있습니다. 이런 연결 리스트의 구조에서 맨 앞을 Head, 맨 마지막을 Tail이라 한다.

 

📍예시로 연결리스트 개념 정리하기

[1, 2, 3, 4, 5]의 배열을 메모리에 저장한다고 생각해보자.(엑셀이나 이차원 배열을 생각해보자)

• 배열 자체의 메모리 : A1
• 1: B1
• 2: C1
• 3: D1
• 4: E1
• 5: F1
• 객체 자체의 메모리 : A2
• a: B2
• b: C2
• c: D2

배열은 위와 같이 각 항의 메모리를 차지하고 있다. 배열은 가깝게 연결되어 있어 다음 값 6을 추가하면 G1에 추가한다.

 

그 다음 값 7을 추가하려고 하는데 이미 A2에는 객체가 들어있고, 그 값들이 배치되어 있다.

 

어쩔 수 없이 E2에 7을 추가한다.

 

여기서 문제는 컴퓨터는 메모리에 데이터가 가까운 것을 찾는다고 했는데, 7이 어디에 있는지를 어떻게 찾을까?

사실, 메모리 값을 저장할때 그 다음 값이 어디로 연결되어있는지 힌트를 남겨준다.

• B1: 값->1, 다음값의 위치->C1
• C1: 값->2, 다음값의 위치->D1
• D1: 값->3, 다음값의 위치->E1
• E1: 값->4, 다음값의 위치->F1
• F1: 값->5, 다음값의 위치->G1
• G1: 값->6, 다음값의 위치->E2
• E2: 값->7, 다음값의 위치->null

위와 같이 값들이 체이닝 되어있는데, 이것을 연결리스트(Linked List)라고 한다.

 

📍JS로 연결리스트 구현하기

👉노드와 연결리스트 생성

class Node {
  next = null; //다음을 가리킴
  constructor(value) { // 1,2,3,4 이런 값을 받음(외부에서 전달받을 값)
    this.value = value;
  } 
}

class LinkedList {
  length = 0; //LinkedList 길이
  head = null; //맨 처음 노드
  // add(삽입)
  // search(검색)
  // remove(삭제)
}

•  클래스 블록 안에서 할당 연산자(=)를 이용해 인스턴스 속성을 지정할 수 있는 문법을 클래스 필드(class field)라고 한다.
• '클래스 필드(class field)'라는 문법을 사용하면 어떤 종류의 프로퍼티도 클래스에 추가할 수 있다
• LinkedList 클래스에 length라는 프로퍼티를 추가하려면 <프로퍼티 이름> = <값>을 써주면 간단히 클래스 필드를 만들 수 있다.
• 클래스 필드의 중요한 특징 중 하나는 User.prototype이 아닌 개별 객체에만 클래스 필드가 설정된다는 점이다.

 

👉연결리스트에 삽입(add), 검색(search), 삭제(remove) 기능 구현

class LinkedList {
 length = 0;
  head = null;

  add(value) {
    if (this.head) { //head에 값이 있을때
      let current = this.head;
      while (current.next) {
        //다음이 없을때까지 계속 반복(다음이 없다는건 값이 비어있다는 것)
        current = current.next;
      }
      current.next = new Node(value); //current.next가 없을때 넣어준다
    } else { //head에 값이 없을때
      this.head = new Node(value); //그냥 해당 값을 추가하면된다
    }
    this.length++; //값이 들어갔으니깐 길이가 하나 길어진다
    return this.length; 
    //length값을 활용하기 위해 return 시킴
    (반환값을 value로 한다면 입력값이랑 동일하기 때문에 아무 의미가 없다)
  }
  
  search(index) {
    return this.#search(index)[1]?.value; //this.#search(index)[1]의 값은 current
  }
  
  #search(index) { //프라이빗 메서드를 사용
    let count = 0; //몇번 넘겼는지 카운트
    let prev;
    let current = this.head; //head가 값이 없을 수 있다
    while (count < index) {
      //주어진 index가 3이면 count는 0,1,2 3번 반복된다
      prev = current;
      current = current?.next;
      //optional chaining(옵셔널 체이닝)을 이용해 프로퍼티가 없는 중첩객체를
      //에러없이 안전하게 접근할수 있다.(null인 경우도 방어됨)
      count++;
    }
    return [prev, current];
  }
  //prev current current.next에서 current를 삭제하려면
  //사실 prev.next가 current로 되어있는 것을 current.next로 넣어주면 된다
  
  remove(index) {
    const [prev, current] = this.#search(index);
    if (prev && current) {
      //search(0)이면 prev가 undefined이고 prev.next를 할 수 없기때문에 prev가 있을때만 실행
      //head가 값이 없으면 current도 undefined이기 때문에 current가 있을때만 실행
      prev.next = current.next;
      this.length--;
      return this.length;
    } else if (current) {
      //index가 0 일때
      this.head = current.next;
      this.length--;
      return this.length;
    }
    //삭제하고자 하는 대상이 없을 때(prev, current가 둘다 없을 경우)
    //아무것도 안함
  }
}

const ll = new LinkedList(); //new LinkedList를 호출해 객체를 생성
ll.length;
ll.add(1); //1
ll.add(2); //2
ll.add(3); //3
ll.add(4); //4
ll.add(5); //5
ll.add(6); //6
ll.search(0); //1
ll.search(3); //4
ll.search(5); //6
ll.search(6); //undefined
ll.remove(4); //5를 지움
ll.remove(4); //5가 지워졌으니깐 6을 지움
ll.search(4); //undefined
ll.remove(4); //undefined

 

👉연결리스트의 시간 복잡도는?

위의 삽입, 검색, 삭제의 시간복잡도 모두 O(n)이다. ('시간복잡도'에 대해서 궁금하다면 클릭!)

add(value) {
    if (this.head) {
      let current = this.head;
      🟨while (current.next) {
      🟨 current = current.next;
      🟨}
      current.next = new Node(value);
    } else {
      this.head = new Node(value);
    }
    this.length++;
    return this.length; 
  }

• 위의 while문(반복문)이 current.next의 값이 없을 때 까지 순차적으로 반복되므로, 입력값에 따라 같은 비율로 증가하는 반복문이 하나 있기 때문에 O(n)이다.

그렇다면 여기서...!

👉삽입을 O(1)로 바꿔보기(tail 사용)

class LinkedList {
  length = 0;
  head = null;
  tail = null; //맨 뒤 추가
 
  //시간복잡도 O(1)
  add_o_1(value) {
    let newNode = new Node(value);
    if (this.head) {
      //head 있을때
      this.tail.next = newNode; //마지막 노드의 next에 새로운 노드 추가
    } else {
      //노드가 아예 없을 때
      this.head = newNode;
    }
    this.tail = newNode; //마지막 노드를 새로운 노드로 업데이트
    this.length++;
    return this.length;
  }
  
  ...

const ll = new LinkedList(); //new LinkedList를 호출해 객체를 생성
ll.length;
ll.add_o_1(1);
ll.add_o_1(2);
ll.add_o_1(3);
ll.add_o_1(4);
ll.add_o_1(5);
ll.add_o_1(6);

 

👉이중 연결 리스트를 만들어 보기(node에 prev 추가)

class Node {
  prev = null; //이전을 가리킴
  next = null; //다음을 가리킴
  constructor(value) {
    this.value = value;
  }
}

class LinkedList {
  length = 0;
  head = null; //맨 앞
  tail = null; //맨 뒤

  //삽입 수정
  add_o_1(value) {
    let newNode = new Node(value);
    if (this.head) {
      //head 있을때
      this.tail.next = newNode; //마지막 노드의 next에 새로운 노드 추가
      newNode.prev = this.tail; //새로운 노드의 prev에 마지막 노드 추가
    } else {
      //노드가 아예 없을 때
      this.head = newNode;
    }
    this.tail = newNode; //마지막 노드를 새로운 노드로 업데이트
    this.length++;
    return this.length;
  }

  //삭제 수정
  remove_prev_next(index) {
    const [prev, current] = this.#search(index); //구조분해할당을 이용해 바로 값을 받는다.
    if (prev && current) {
      //search(0)이면 prev가 undefined이고 prev.next를 할 수 없기때문에 prev가 있을때만 실행
      //head가 값이 없으면 current도 undefined이기 때문에 current가 있을때만 실행
      if (current === this.tail) {
        this.tail = current.prev; //tail을 삭제하고 삭제되는 노드의 이전값을 tail에 넣어준다.
        prev.next = null;
        // this.tail.next = null;//next
      } else {
        prev.next = current.next;
        current.next.prev = current.prev;
      }
      this.length--;
      return this.length;
    } else if (current) {
      //index가 0 일때
      this.head = current.next;
      this.length--;
      return this.length;
    }
    //삭제하고자 하는 대상이 없을 때(prev, current가 둘다 없을 경우) 아무것도 안함
  }
}

const ll = new LinkedList(); //new LinkedList를 호출해 객체를 생성
ll.length;
ll.add_o_1(1);
ll.add_o_1(2);
ll.add_o_1(3);
ll.add_o_1(4);
ll.add_o_1(5);
ll.add_o_1(6);
ll.remove_prev_next(4); //5를 지움
ll.search(4); //undefined
ll.search(4); //5
ll.remove_prev_next(4); //5가 지워졌으니깐 6을 지움
ll.search(4); //undefined

 

📍마무리

드디어 연결리스트의 개념을 제대로 이해 완료! 그리고 강의 마지막에 '삽입 시간복잡도를 O(1)로 바뀌보기'와 '이중연결리스트를 만들어보기' 숙제가 생겨 쉽진 않았지만 해결해서 뿌듯했다.(맞는지는 모르겠지만 🤣 🤣)

아 그리고 강의를 잘 이해하기 위해선 역시나 자바스크립트 문법을 공부해야겠단 생각이 들었...(이것도 나중에 정리해봐야지 꼭...)