[Linear] Linked List(단방향)

Linked List는 노드값에 데이터와 헤더값을 기본으로 데이터를 찾아가는 방식임.

 

데이터(실제 데이터 공간), 헤더(주소 데이터공간)을 의미. 

 

헤더에는 내 앞에 있는 노드의 주소를 저장한다. 

 

EX) 선생님이 철수에게 "이 화분 누가 깨뜨렸어?" 라고 묻자. 철수는 영희를 가리키며, "영희가 그랬어요."

 

영희는 "빡구가 그랬어요" 라며 손가락으로 가리킨다. 이때 손가락 부분이 헤더라고 보면 이해하기 쉽다.

 

장점으로는 삽입, 삭제가 많은 데이터 리스트에 사용한다.

 

특징은 데이터 중간에 삽입, 삭제 가능하며, 동적어레이로 크기 조절이 자유롭다. 따라서 메모리 공간을 절약할 수 있음. 

 

하지만, 계속 단서를 찾아가기 때문에 접근 속도가 느리다.

 

새 Node[DATA, HEAD] 생성
LinkedList 만들기

추가하기.
append(inputData) 만들어준다.
append 안에 New Node[data, head] (객체)를 만들어준다.
New Node[data]에 inputData 저장한다.
노드위치값을 추적하기 위한 최근값의 변수를 생성한다. 
(기존 Node 객체의 내부를 수정하면서 진행해야 함).
새로 추가되는 값이 NULL인지, 아닌지를 고려해야함.
null이면 head값이 New node의 주소값을 저장한다.
null이 아니면, 최근값이 New Node의 헤더값을 저장하고, 최근값의 마지막 값을 찾는다.
최근값의 마지막값에 노드주소를 저장한다.

삭제하기.
데이터가 리스트의 첫번째 데이터인지 아닌지에 따라 두가지 경우를 생각해야함.
첫번째 노드를 삭제하면 head를 두번째 노드로 교체.
그외의 노드를 삭제하면 삭제되는 노드의 앞 노드의 헤더(next)를 삭제되는 노드의 다음 노드의 주소값으로 교체.

중간에 삽입하기.
데이터를 처음, 중간 or 맨끝에 추가하는 경우로 나누어 진다.
처음에 추가하면 추가되는 노드의 헤더값이 처음 노드값으로 변경되고
중간이나 끝에 추가 되면 이전값은 최근값이 되고, 최근값은 마지막값이 된다.

1. functional instantiation (단방향 리스트)

//next : list의 다음노드에 대한 포인터.
//length : 우리가 가지고 있는 list의 items수를 저장.
//head : 첫번째노드를 저장.
function LinkedList(){
  let Node = function(item){
    this.item = item;
    this.next = null;
  };
  
  let length = 0;  
  let head = null;
  //1.리스트 끝에 아이템 추가.  이경우는 2가지 경우 고려, list가 비어있을때와 그렇치 않을때. 
  this.append = function(item){
    let node = new Node(item);
    let current;
    
    if(head === null){ //head가 null이면 비어있는거임. 첫번쨰 요소가 되는거임.
      head = node;
    }else{ //비어있지 않으면 기존꺼는 어짜피 head임, 추가분은 n 번째가 되는거임.
      current = head;
      //마지막 item을 찾을때까지 loop를 돌린다.
      while(current.next){
      current = current.next; //마지막 노드의 next값은 null이다. 왜? 마지막은 없으니깐 가르킬 주소가 없음.
      }
    //마지막을 찾았으면 마지막 노드에 append할 노드를 붙여줘야함.
      current.next =node;
    }    
    length++; //추가끝났으면 length가 증가.   
  };  
 
  // 2.리스트의 원하는 위치에 있는 아이템 제거. 2개를 고려해야함. 첫번째요소제거, 첫번째가 아닌 요소를 제거.
  this.removeAt = function(position){
    //제거를 원하는 position값이 범위를 벗어났는지 확인.
    if(position > -1 && position < length){
      let current = head; //리스트의 1번째요소 참조. 
      let previous;
      let index = 0;
    
    //첫번째 item 제거 
    if(position === 0){  //0번째 값을 삭제하면 1번째 값이 0번째가 되는 것임. 그래서 head가 0번째에서 1번째노드 가르키는 주소 current.next가 됨.
      head = current.next;
    }else{ //position이 0이 아니면, 현재값은 current.next값을 가르키고, 이전값은 current값이 된다.
      while(index++ < position){  //원하는 위치까지 반복할꺼임. 찾아야함.       
        previous = current;   //원하는 위치의 값을 빼면, 현재값은 이전값이 되고, 빠진값의 다음값은 현재값이 된다.                
        current = current.next;
      }            
      //중간꺼를 제거한 후 이전값과 현재값을 이어줘야함.
      previous.next = current.next;      
    }
    //하나 빠지니깐 삭제.
    length--;
    return current.item;
    }else{ //범위에 벗어났다면, 값이 없는거니깐 null.
      return null;
    }  
  };  
  
   //3.원하는 위치에 새로운 아이템을 집어넣는다.  2가지 경우 고려, 첫번째위치, 첫번째를 제외한 위치.
   this.insert = function(position, item){
     //원하는 위치에 넣으려면, 범위내에 있는지 확인.
    if(position >= 0 && position <= length){
      let node = new Node(item);
      let current = head;
      let previous;
      let index =0;
      //첫번째 위치에 넣는 경우.
      if(position === 0){
        node.next = current;
        head = node;
      }else{
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        node.next = current; //앞에 추가된거니깐 node.next가 current가 됨.
        previous.next = node;
      }
      //추가됐으니깐 길이 증가.
      length++;
      return true;
    } else {
      return false;
    }     
     
   };
  //4.연결선 만들기.
  this.toString = function(){
    let current = head;
    let string ='';
    while(current){  //current가 null값이 되면 loop 탈출.
      string += current.item + (current.next ? '→' : '');
      current = current.next;
    }
    return string;
  }; 

  //5.리스트의 아이템의 인덱스 위치를 리턴, 없으면 -1 리턴. 
  this.indexOf = function(item){
    let current = head;
    let index = -1; //원래 인덱스는 0부터 시작, 없으면 -1리턴해주면 되기때문.
    while(current){
      if(item === current.item){
        return index;
      }
      index++;
      current = current.next;      
    }
    return -1;
  }; 
  
  //6.리스트에서 아이템 제거 , 굳이 필요없음, 재사용하려면 가져다 써도 됨.
  this.remove = function(item){
   // let index = this.indexOf(item);
   // return this.removeAt(index);
   
    let current = head;
    let previous;
    if(current.item === item){
        head = current.next;
    } else {
        while(current.item !== item) {
            previous = current;
            current = current.next;
        }
        previous.next = current.next;
    }
    length --;   
  }; 
  
  //7.비어있으면 TRUE 아니면 FALSE
  this.isEmpty = function(){
    return length === 0;
  }; 
  this.size = function(){return length}; 
  
  this.getHead = function(){
    return head;
  }
  
  
}

let list = new LinkedList();
list.append(15);
list.append(10);
list.append(13);
list.removeAt(1);
list.size();
list.insert(2,20);
list.getHead();
list.toString();