자료구조 Linked List

Linked List

연결 리스트라고도 불리는 자료구조이다.
배열과 비슷하면서도 다르다는 느낌이 들었다.
각각의 노드는 데이터와 다음 노드가 무엇인지 알려주는 주소(링크)를 가지고 있다.
Head는 첫 번째 요소를 가르키고, tail은 마지막 요소를 가르킨다.

그림을 보고 코드를 본다면 이해하기 수월할 것이다!

head: {0: '첫번째obj', next: {1: '두번째obj', next: {2: '세번째obj', next: null}}}}
tail: {2: '세번째obj', next: null}

연결리스트는 링크를 통해서 데이터 추가, 삭제, 탐색이 가능하고
데이터나 링크 둘 중에 하나만 가지는 것은 불가능하다. (마지막 노드의 링크는 Null을 가르킨다)

배열보다 메모리를 적게 사용하지만 링크 메모리가 따로 필요하고 링크 하나에 4byte 메모리를 차지한다.

자바스크립트로 Linked List 구현하기

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

Linked List 슈도코드

1.addToTail
1.1. 값을 넣은 새로운 노드를 만든다.
1.2. 만약 헤드가 비었다면(첫 생성) 머리와 꼬리에 새로운 노드를 할당한다.
1.3. 아니라면 꼬리(링크 끝)에 추가해준다
1.4. 꼬리(링크 끝)을 새로 추가한 노드로 바꿔준다.
1.5. 사이즈 + 1

2. Remove
2.1. head가 없을 때를 생각해서 head가 null일땐 undefined를 반환한다.
2.2. 헤드의 값이 찾으려는 값과 같으면 헤드를 next로 바꿔준다.
2.3. 변수 2개를 선언해서 각각 첫노드와 다음노드를 할당한다.
2.4. 현재 첫노드는 위에서 걸렸으니 다음노드와 값을 비교하고 같으면 현재노드의 다음노드에 다다음노드를 할당하고 반복문 브레이크
2.5. 아니라면 현재노드 변수를 다음노드로 바꾸고 다음노드변수를 다다음노드로 바꾼다를 반복
2.6 사이즈 - 1

3.getNodeAt
3.1. 첫번째 노드를 변수에 담아 현재 노드로 저장한다.
3.2. 만약 입력받은 인덱스가 사이즈보다 크다면 없는거니 undefined를 반환한다.
3.3. 인덱스만큼 반복문을 돌려서 현재 노드를 다음 노드로 바꿔가며 찾으려는 노드까지 들어간다.
3.4. 현재노드를 반환

4.contain
4.1. 첫번째 노드를 변수에 담아 현재 노드로 저장한다.
4.2. 현재 리스트 사이즈만큼 반복문을 돌려서 현재 노드의 값과 입력받은 값이 같으면 True 반환
4.3.아니면 현재노드를 다음노드로 바꾸고 반복
4.4. 반복문이 끝나면 False 반환

5.Indexof
5.1. 첫번째 노드를 변수에 담아 현재 노드로 저장한다.
5.2. 카운트를 세고 저장할 변수 선언
5.3. 리스트 사이즈만큼 반복문을 돌려 현재 노드의 값과 입력받은 값이 같으면 카운트를 반환
5.4. 아니면서 다음노드가 null이 아니면 카운트 + 1, 현재 노드를 다음 노드로 바꿈
5.5. 만약 끝까지 없으면 -1을 반환

6.size
6.1. 현재 사이즈 반환

Linked List JS코드

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }
  
  addToTail(value) {
    let newnode = new Node(value)
    if(this.head === null){
      this.head = newnode
      this.tail = newnode
    }
    else {
      console.log(this.head)
      this.tail.next = newnode
      this.tail = newnode
    }
    this._size++
 

  }
  
  remove(value) {
    if(this.head === null){
      return undefined
    }
    let node = this.head
    let nextnode = this.head.next

   
    if(this.head.value === value){
      this.head = this.head.next
      return this
    }
    for(let i = 0; i < this._size; i++){
      if(nextnode.value === value){
        node.next = nextnode.next
        break;
      }
      else{
        node = nextnode
        nextnode = nextnode.next
      }
    }
    this._size--
    // return this
  }
  
  getNodeAt(index) {
    let findnode = this.head
    if(index > this._size){
      return undefined
    }
    for(let i = 0; i < index; i++){
      findnode = findnode.next
    }
    return findnode
  }
  
  contains(value) {
    let findnode = this.head
    
    for(let i = 0; i < this._size; i++){
    if(findnode.value === value){
      return true
    }
    else{
      findnode = findnode.next
    }
  }
    return false
  }
  
  indexOf(value) {
    let  findnode = this.head
    let count = 0
    for(let i = 0; i < this._size; i++){
      if(findnode.value === value){
        return count
      }
      else if(findnode.next !== null){
        count++
        findnode = findnode.next
      }
      else if(findnode.next === null) {
        return -1
      }
    }
 
  }
  
  size() {
    return this._size
  }
}