1. 연결 리스트-Node, printNode(), append()

연결 리스트 (Linked List)

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

- 배열에 비해 자료 추가/삭제가 쉽지만 자료를 찾을 때는 무조건 순회하는 과정이 필요하다는 단점이 있다.

(찾으려는 학생이 100만 명일 때는 배열이 훨씬 효율적)

- Node() : data와 point(연결)를 가지고 있는 객체

 

노드 추가 / 삭제

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

//LinkedList(): head와 length를 가지고 있는 객체
function LinkedList() {
  this.head = null;
  this.length = 0;
}

// size(): 연결 리스트 내 노드 갯수 확인
LinkedList.prototype.size = function() {
  return this.length;
}

//isEmpty(): 객체 내 노드 존재 여부 파악
LinkedList.prototype.isEmpty = function() {
  return this.length === 0;
}

let ll = new LinkedList();
console.log(ll); // LinkedList { head: null, length: 0 }

ll.head = new Node(123);
ll.length++;
console.log(ll); // LinkedList { head: Node { data: 123, next: null }, length: 1 }

ll.head.next = new Node(456);
ll.length++
console.log(ll);
/*
LinkedList {
  head: Node { data: 123, next: Node { data: 456, next: null } },
  length: 2
}
*/

 

 

printNode() 풀이

- node가 연결되어 있다는 것을 보기 쉽게 표현할 수 있다.

1. node에 this.head 값을 넣어준다. 초기값은 null이다.

2. node가 null이 아닐 때까지 반복한다. node에는 node.next가 업데이트된다.

3. 반복이 끝났으면 null을 출력한다.

4. 연결된 node를 깔끔하게 볼 수 있도록 출력한다.

LinkedList.prototype.printNode = function(){
  for(let node = this.head; node != null; node = node.next){
    process.stdout.write(`${node.data} -> `);
  }
  console.log("null");
}

ll.printNode(); // 1 -> 10 -> 100 -> null

 

append() 풀이

- ll.head.next = new Node(456)처럼 일일이 계속 추가해주는 것이 아니라 자동으로 맨 마지막 node에 이어지도록 한다.

1. value값이 들어오면 new Node를 만든다.

2. this.head가 null이라면(node가 없음) node를(1번에서 만들어진 node)로 업데이트 한다.

3. this.head가 null이 아니라면 current(this head를 가리킴)의 next(기본값이 null) 값을 업데이트한다.

예를 들어 밑에 예시처럼 1 -> 10 -> 100을 연결한다는 뜻!

4. current.next(this.head.next와 같음)는 node(1번에서 만들어진 node)로 업데이트 된다.

5. this.length를 통해 노드 길이가 1씩 늘어난다.(사이즈가 늘어난다.)

6. 이제 if문은 해당되지 않고(this.head는 업데이트 되었기 때문에) while값을 반복한다. 

 

(깨알 while문 복습)

- 조건이 참일 때 반복문이 수행, 거짓이면 그냥 넘어감

//append(): 연결리스트 가장 끝에 노드 추가
LinkedList.prototype.append = function(value){
  let node = new Node(value);
    current = this.head;

  if (this.head === null){
    this.head = node;
  } else {
    while(current.next != null){
      current = current.next;
    }
    current.next = node;
  }
  this.length++;
};

ll.append(1);
ll.append(10);
ll.append(100);

ll.printNode(); // 1 -> 10 -> 100 -> null
console.log(ll.size()); // 3

 

insert() 풀이

- append()가 맨 끝 Node를 추가하는 거라면 insert를 통해 position을 지정해줄 수 있다.

- default 값은 0이며 맨 앞에 추가된다.

 

1. 먼저 position에 0 이하나 주어진 길이보다 큰 값이 올 경우는 false

2. value를 데이터로 가지는 새로운 node를 생성한다.

3. current로 head를 계속 바꿔주고, index만큼 수행할 수 있도록 한다.(몇번째 자리를 바꿀 것인지에 사용) prev는 이전 노드값을 저장해서 새로운 노드와 이전 노드가 연결될 수 있도록 한다.

4. position 값이 없을 때(0일 때), current(기존의 head가 가리키는 null)를 node.next로 이어준다. 

5. this.head(현재 head)는 node를 가리키면서 이어준다.

6. position 값이 있을 때, while 반복문이 true가 되면서 position 값만큼 수행된다.

7. current(this.head)를 prev에 업데이트, current.next를 current에 업데이트한다.

8. prev는 current(this.head)를 가리키고 current는 node를 가리키면서 기존 연결 리스트에 추가된다.

9. while문을 통해 position만큼 반복하면서 prev와 current가 해당 자리만큼 옮겨간다.

10. node.next를 current에 연결하고 prev.next는 node에 연결한다.

// insert(): position 위치에 노드 추가
LinkedList.prototype.insert = function(value, position = 0){
  if(position < 0 || position > this.length){
    return false;
  }

  let node = new Node(value),
    current = this.head,
    index = 0, 
    prev; // 이전 노드값 저장

    if(position === 0){
      node.next = current;
      this.head = node;
    } else {
      while(index++ < position){
        prev = current;
        current = current.next;
      }

      node.next = current;
      prev.next = node;
    }
  
    this.length++

    return true;
}

let ll = new LinkedList();

ll.insert(1);
ll.insert(10);
ll.insert(100);

ll.insert(2, 1);
ll.insert(3, 3);

ll.printNode(); //100 -> 2 -> 10 -> 3 -> 1 -> null
console.log(ll.size()); // 5