Linked List

# Linked List

 - 각 원소의 주소값이 연속해서 붙어 있지 않고, 원소들이 각각 다음에 올 원소의 주소값을 가리키고 있는 형태

 - 연결 리스트에서 각 원소들을 노드(Node) 라고 부름

 - 크기가 동적인 자료구조

 - 단일연결리스트(Singly-Linked List)와 이중연결리스트(Doubly-Linked List)가 있음

 

 

 

## 단일 연결 리스트 (Singly-Linked List)

 

 - 노드들의 연결 방향이 한쪽 방향으로만 연결되어 있음

 - 단일연결리스트의 노드는 다음에 올 노드의 주소와 자신의 값을 가지고 있어 한쪽 방향으로만 탐색이 가능

 

 

## 이중 연결 리스트 (Doubly-Linked List)

 

 

 - 노드들의 연결 방향이 양쪽 방향으로 연결되어 있음

 - 이중연결리스트의 노드는 자신의 값과 이전에 올 노드의 주소, 다음에 올 노드의 주소를 모두 가지고 있어 양방향으로의 탐색이 가능

 

 

 ## Linked List의 사용 예시

   - 스택과 큐의 구현

   - 동적 메모리 할당

   - 웹 브라우저의 이전 페이지, 다음 페이지

   - 이미지 뷰어, 음악 플레이어

 

 

 ## Linked List의 Property

   - value :  각각의 노드가 가지는 프로퍼티, 해당 노드의 값이 저장되어 있음

   - next :  각각의 노드가 가지는 프로퍼티, 다음에 올 노드의 주소(키)값이 저장되어 있음

   - head :  Linked List의 프로퍼티, 가장 앞쪽에 위치하는 노드를 가리킴

   - tail :  Linked List의 프로퍼티, 가장 뒤쪽에 위치하는 노드를 가리킴

 

 

 ## Linked List의 Method

 

   - add :  Linked List에 새 노드를 추가

add 연산 (tail에 노드 추가)
  1. 새 노드를 하나 생성
  2. head가 빈 노드라면
       head 값을 새로 생성된 노드로 변경
  3. tail이 빈 노드가 아니라면
       현재 tail의 next를 새로 생성된 노드로 변경
  4. tail 값을 새로 생성된 노드로 변경
  5. 리스트의 크기를 하나 증가
  

 

   - remove :  Linked List에서 노드를 삭제

remove 연산
  1. 제거될 노드의 값과 일치하는 값을 찾을 때까지 리스트를 순회
       제거될 노드의 값과 일치하는 값을 찾았다면
         반복문 종료
       노드를 끝까지 순회했지만 일치하는 값을 찾지 못했다면
         반복문 종료
  2. 제거될 노드의 이전 노드의 next를 제거될 노드의 다음 노드 값으로 갱신
  3. 리스트의 크기를 하나 감소
  4. 제거된 노드를 반환
       

 

   - contains :  Linked List에서 특정 값을 갖는 노드가 존재하는지 true / false 로 나타냄

contains 연산
  1. 찾을 노드의 값과 일치하는 값을 찾을 때까지 리스트를 순회
       찾을 노드의 값과 일치하는 값을 찾았다면
         반복문 종료
       노드를 끝까지 순회했지만 일치하는 값을 찾지 못했다면
         반복문 종료
  2. 찾는 노드가 있었다면 true 반환 / 없었다면 false 반환
       

 

   - indexOf :  Linked List에서 특정 인덱스(주소, 키값)를 갖는 노드를 찾아 반환

indexOf 연산
  1. 찾을 노드의 값과 일치하는 인덱스를 찾을 때까지 리스트를 순회
       찾을 노드의 값과 일치하는 인덱스를 찾았다면
         반복문 종료
       노드를 끝까지 순회했지만 일치하는 인덱스를 찾지 못했다면
         반복문 종료
  2. 찾는 노드가 있었다면 해당 인덱스 반환 / 없었다면 -1 반환
       

 

   - getNodeAt :  Linked List에서 특정 값을 갖는 노드를 찾아 반환

getNodeAt 연산
  1. 주어진 인덱스에 도달할 때까지 리스트를 순회
       해당 인덱스에 도달했다면
         반복문 종료
  2. 해당 인덱스에 노드가 있었다면 노드 반환 / 없었다면 undefined 반환