연결리스트

연결리스트 구현

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

class LinkedList{
  constructor(head=null){
    this.head = head;
  }
  
  // 전체 순회
  circuit(){
    let temp = this.head;
    while(temp){
      console.log(temp.data);
      temp = temp.next;
    }
  }
  
  // 리스트 뒤에 삽입
  push(data){
    const new_node = new Node(data);
    // 리스트가 비어있을때 처리
    if(this.head===null){
      this.head = new_node;
      return;
    }
    let last = this.head;
    // 맨 마지막 노드 찾기
    while(last.next){
      last = last.next;
    }
    last.next = new_node;
  }
  
  // 리스트 앞에 삽입
  unshift(data){
    const new_node = new Node(data);
    // 리스트가 비어있을때 처리
    if(this.head===null){
      this.head = new_node;
      return;
    }
    const temp = this.head;
    this.head = new_node;
    new_node.next = temp;
  }
  
  // 매개변수가 data일때 제거
  remove(data){
    let curr = this.head;
    let prev = null;
    // 리스트 맨앞의 노드가 삭제하려는 노드일 경우 처리
    if(curr && curr.data === data){
      this.head = curr.next;
      curr = null;
      return;
    }
    // 삭제하려는 data를 찾을때까지 반복문 돌리기 
    while(curr){
      if(curr.data === data) break;
      prev = curr;
      curr = curr.next;
    }
    // 삭제하려는 data가 리스트에 없을때 
    if(curr===null) return;
    // 삭제과정
    prev.next = curr.next;
    curr = null;
  }
  
  // 매개변수가 노드일때 제거
  remove(node){
    if(node===null) return;
    if(node.next===null) return;
    let next_node=node.next;
    node.data = next_node.data;
    node.next = next_node.next;
    next_node = null;
  }
}

리스트를 역으로 정렬(스택 방식)

입력: 1 -> 2 -> 3

답: 3 -> 2 -> 1

function reverseList_stack(head){
    if (head===null) return;
    let stack = [];
    let curr = head;
    // 리스트를 스택에 넣기(마지막 노드는 제외)
    while (curr.next){
      stack.push(curr);
      curr = curr.next;
    }
    let first = curr;
    // 스택에서 노드를 꺼내서 다시 연결
    while (stack.length>0){
      curr.next = stack.pop();
      curr = curr.next;
    }
    curr.next = null;
    return first;
}

실행결과

const linked_list =  new LinkedList();
linked_list.push(11);
linked_list.push(12);
linked_list.push(13);
linked_list.unshift(10);
const reversed_first_node = reverseList_stack(linked_list.head);
const newList = new LinkedList(reversed_first_node);
newList.circuit(); // 13, 12, 11, 10 

연결리스트의 순환 유무파악

노드를 Set에 저장 후, 중복이 발생하면 순환이 존재

function hasCycle(head){
  let curr = head;
  const node_set = new Set();
  while(curr){
  // 노드들을 set에 한번 순회하면서 저장하고, 
  // 노드가 set안에 들어 있으면 (두번째 순회가 발생하므로) 순환이 존재.
    if(curr in node_set) return true;
    node_set.add(curr);
    curr = curr.next;
  }
  return false;
}

두수 더하기

연결리스트 두개가 주어지고 둘을 더한 하나의 리스트를 반환

입력: 1 -> 2 -> 3 , 4 -> 5 -> 6

답: 5 -> 7 -> 9

function addTwoNumbers(head1, head2){
  let num1 = "";
  let num2 = "";
  let head1_curr = head1;
  let head2_curr = head2;
  while(head1_curr){
    num1 += String(head1_curr.data);
    head1_curr = head1_curr.next;
  }
  while(head2_curr){
    num2 += String(head2_curr.data);
    head2_curr = head2_curr.next;
  }
  const answer = String(parseInt(num1) + parseInt(num2));
  let node = new Node(0);
  let curr = node;
  for (chr of answer){
    curr.next = new Node(parseInt(chr));
    curr = curr.next;   
  }
  curr.next = null;
  return node.next; // 새로운 head를 리턴
}

실행결과

const linked_list = new LinkedList(); // 1 -> 2 -> 3
linked_list.push(1);
linked_list.push(2);
linked_list.push(3);
const linked_list2 = new LinkedList(); // 9 -> 1 -> 4
linked_list2.push(9);
linked_list2.push(1);
linked_list2.push(4);
const new_head = addTwoNumbers(linked_list.head, linked_list2.head);
const new_list = new LinkedList(new_head);
new_list.circuit(); // 1 -> 0 -> 3 -> 7