하루5분코딩"Linked list"

## Linked list :노드의 연결로 이루어진 자료구조

노드에 다음번 노드의 주소를 가지고 있는 형태이다.

  • linked list 는 배열과 비교했을때 특정 데이터를 검색하는 시간이 오래 소유된다. index 를 통해서 찾는 배열과 달리 하나 하나 찾아봐야 하기 때문이다.

    ✓ 노드 추가
    ✓ 노드 삭제

  • 두 자료를 보면 다음 요소의 주소를 알기 때문에 배열보다 요소를 추가하거나 삭제하기 쉽다. 하지만 다음요소의 주소만 알기 때문에 전에 있던 요소를 알수 없다.

  • 이와 같이 단인 연결 리스트이중 연결 리스트로 존재한다.
    linked list는 다음 요소의 정보만 가지고 있기 때문에 탐색이 불가능 한데, 이러한 단점을 보완할수 있는게 이중 연결 리스트다.

✓Method

  • addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가합니다.
  • remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)합니다
  • getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 해당 인덱스에 노드가 없다면 undefined를 반환합니다.
  • contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
  • indexOf(value) - 주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.

✓ 사용

  addToTail(value) {
    let node = new Node(value);
    if(!this.head){
      this.head = node;
      this.tail = node;
    }
    this.tail.next = node;
    this.tail = node;
    this._size ++
  } 
  remove(value) {
    let find = this.head
    while(find) {
      if(find.value === value){
        find.value = find.next.value
        find.next = find.next.next
        this._size --
      }
      find = find.next
    }
  }
  getNodeAt(index) {
    let count = 0;
    let find = this.head
    while(find){
      if(count === index){
        return find
      }
      find = find.next
      count++
    }
    return undefined
  }
 contains(value) {
    let find = this.head
    while (find){
      if(find.value === value){
        return true;
      }
      find = find.next
    }
    return false;
  }
  indexOf(value) {
    let count = 0;
    let find = this.head
    while(find){
      if(find.value === value ){
        return count 
      }
      find = find.next
      count++
    }
    return -1
  }
  size() {
    if(this._size < 1){
      return 
    }
    return this._size
  }

좋은 웹페이지 즐겨찾기