단일 연결리스트 (Singly Linked Lists)

주요 용어 설명

• Node : 리스트의 각 요소 (val,next)
• Head : 리스트의 시작 부분
• Tail : 노드의 마지막 요소

단일 연결리스트의 장단점 및 특징, 사용

사용

• 무작위 접근은 필요하지 않고 순서를 가진 리스트 형태의 데이터가 필요한 상황이라면 혹은 10번째, 50번째 요소에 접근할 필요가 없고 순서대로 요소들에 접근해도 되는 상황이라면 단일 연결리스트를 사용하는것이 좋다

특징

• 각 노드의 값에는 숫자, 배열, 스트링 모두 저장 가능하다
• 배열과 달리 인덱스가 없다
• 리스트는 삽입과 삭제에 특화 되어 있다. 특히 처음과 끝에 삽입 삭제가 쉽다.

장점

• 배열의 경우 원소의 삭제 또는 삽입 이벤트가 있을때 인덱스의 변화가 생겨 시간복잡도 O(n)을 가지지만 리스트의 경우 시간복잡도 O(1)을 가져서
  대량의 데이터에서 순서가 상관 없는경우 더 유리하다.
• 삽입과 삭제를 맨 앞 부분에서 자주 해야 하는 경우에는 배열에 비해 좋다.

단점

• 인덱스가 없기 때문에 배열 처럼 특정 인덱스의 원소에 접근이 불가능하고 항상 처음 Head에서부터 탐색을 해야한다.

시간복잡도

• 삽입(Insertion) - O(1)
• 삭제(Removal) - O(1)(처음일 경우) or O(N) (가장 안좋은 경우는 가장 마지막 삭제)
• 검색(Searching) - O(N)
• 접근(Get,Accesee) - O(N)

노드 및 리스트 생성자 생성

• Node : 노드 자신의 값과 다음을 가르키는 next를 가진다.
• SinglyLinkedList : 리스트의 시작을 가르키는 head와 마지막을 가르키는 tail, 사이즈 length를 가진다.

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

class SinglyLinkedList{
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

리스트 Push method 구현

1. 노드 생성
2. head 값이 null 인지 체크
3. head 값이 null 일 경우 head와 tail값 초기화
4. head 값이 null이 아닌 경우 tail값을 바꿔 준다.
5. 사이즈를 증가시켜준뒤 리턴한다.

push(val){
  let newNode = new Node(val)
  if(!this.head){
    this.head = newNode;
    this.tail = this.head;
  }else{
    this.tail.next = newNode;
    this.tail = newNode;
   }
   this.length++
   return this
}

리스트 Pop method 구현

1. 리스트에 노드가 없다면 return undefined
2. 리스트 전체를 tail까지 탐색한다.
3. tail까지 가는 변수와 tail 전까지 가는 변수를 생성한다.
4. 뒤에서 두번째 노드의 next를 null로 만들어준뒤 tail의 값을 뒤에서 두번째 노드로 변경한다.
5. 길이 - 1
6. 제거된 노드를 리턴한다.

pop(){
  if(!this.head) return undefined
  let fastNode = this.head
  let currentNode = fastNode
  while(fastNode.next){
    currentNode = fastNode
    fastNode = fastNode.next
    }
   this.tail = currentNode
   this.tail.next = null
   this.length--
   if(this.length === 0){
    this.head = null
    this.tail = null
   }
   return fastNode
}

리스트 Shift method 구현

• 리스트의 시작 부분에 있는 노드 삭제

1. 리스트에 노드가 없다면 return undefined.
2. 노드가 있으면 변수에 헤드를 저장.
3. 헤드의 next를 바꿔준다.
4. 길이 - 1
5. 삭제된 헤드를 리턴해준다.

shift(){
  if(!this.head) return undefined
  let headNode = this.head
  this.head = headNode.next
  this.length--
  if(this.length===0){
    this.tail = null
    }
  return headNode
}

리스트 Unshift method 구현

• 리스트의 시작부분에 노드를 추가하는것

1. 노드 생성.
2. head가 있는지 체크하고 없으면 head,tail모두 새로운 노드가 되도록 설정한다.
3. head가 있다면 새로 생성된 노드의 next를 현재 head로 설정해주고 리스트의 head를 새로 만든 노드로 설정한다.
4. 길이 + 1
5. 리스트 리턴

unshift(val){
  let newNode = new Node(val)
  if(!this.head){
    this.head = newNode
    this.tail = this.head
  }else{
    newNode.next = this.head
    this.head = newNode
  }
  this.length++
  return this

리스트 Get method 구현

• 숫자나 인덱스, 위치를 입력하는 메소드로 해당 위치의 노드를 출력해준다.
• head에서 시작하여 n번째 위치하는 노드를 찾아 출력해준다.

1. 함수에 인덱스를 받는다.
2. 인덱스의 값이 음수 or 길이보다 크거나 같은 경우 return null.
3. 인덱스에 도달 할때까지 루프를 돈다.

get(idx){
  if(idx < 0 || this.length <= idx) return null
  let currentNode = this.head
  for(let i=0; i<idx; i++){
    currentNode = currentNode.next
  }
  return currentNode
}

리스트 Set method 구현

• set(position|index , val) 해당 위치 노드값을 바꾼다.

1. get 함수를 이용하여 위치를 확인한다.
2. 노드를 찾을 수 없다면 return false
3. 찾았다면 값을 바꾸고 출력 해준다.

set(idx,val){
    let foundNode = this.get(idx)
    if(foundNode){
      foundNode.val = val
      return true
    }
    return false
  }

리스트 Insert method 구현

• insert(position|index , val) 해당 위치에 새로운 노드를 삽입한다.

1. 인덱스의 값이 음수 or 길이보다 클 경우 return false.
2. 인덱스의 값이 길이와 같다면 맨뒤에 삽입해준다.(Push method)
3. 인덱스의 값이 0이면 Unshift method 사용
4. 1,2,3 조건 모두 아닐경우 get method 를 사용하여 index-1을 찾는다(삽입 전 노드를 찾아야함)
5. 변수를 생성하여 찾은 노드의 next 값을 저장한다.
6. 새로운 노드를 생성한다.
7. 찾은 노드의 next 값을 새로만든 노드로 바꿔준다.
8. 새로만든 노드의 next 값을 원래 next였던 노드에 연결해준다.
9. 길이 + 1

insert(idx,val){
  if(idx < 0 || this.length < idx) return false
  // ! = false !! = true
  if(idx === this.length) return !!this.push(val)
  if(idx === 0) return !!this.unshift(val)

  let preNode = this.get(idx-1)
  let tmp = preNode.next
  let newNode = new Node(val)
  preNode.next = newNode
  newNode.next = tmp
  this.length++
  return true
}

리스트 Remove method 구현

• remove(index) 해당 인덱스에 위치한 값을 제거한다.

1. 인덱스가 0보다 작거나 길이보다 크거나 같다면 return undefined
2. 인덱스가 길이-1 같은경우(마지막) Pop method 사용
3. 인덱스가 0이라면 shift method 사용
4. 1,2,3의 경우가 아니라면 get(index-1)을 하여 삭.
5. 삭제할 노드의 전 노드를 찾는다.
6. 찾은 노드의 next를 next.next로 설정한다
7. 길이 - 1
8. 삭제한 노드의 값을 출력한다.

remove(idx){
  if(idx < 0 || this.length <= idx) return undefined;
  if(idx === 0) return this.shift()
  if(idx === this.length-1) return this.pop()

  let preNode = this.get(idx-1)
  let delNode = preNode.next
  preNode = delNode.next
  this.length--
  return delNode
}

리스트 Reverse method 구현

• 리스트를 그 상태로 뒤집는것이다.
• 사본을 만들 필요가 없다.(복사를 해서 새로운 리스트를 출력하는것이 아니다.) => 앞으로 순회를 하면서 하나씩 뒤집는다.

1. nextNode, preNode, currentNode(head에서 시작) 변수를 생성한다.
2. head와 tail을 바꾼다
3. 루프를 돌며 바꿔준다.

reverse(){
  let currentNode = this.head
  let preNode = null
  let nextNode;
  this.head = this.tail
  this.tail = currentNode
  while(currentNode){
    nextNode = currentNode.next
    currentNode.next = preNode
    preNode = currentNode
    currentNode = nextNode
  }
  return this
}