# 단일 연결리스트

reference: [출처](https://www.udemy.com/course/best-javascript-data-structures/)

<figure><img src="/files/3ifVyB6ZIaa8TpZGJSGN" alt=""><figcaption></figcaption></figure>

**linked list 란?**

* **head**(linked list의 시작 node), **tail**(마지막 node), **length**를 가지고 있는 자료구조
* 다음 데이터 element를 가리키는 index없이(접근할 index 없음), 다수의 data element(**node**)로 구성
* 각 node는 value와 pointer를 가지고 있고 string 혹은 number 형태로 저장
* 각 node는 다음 node를 가리키는 정보 역시 저장하고 있어야 하며, 다음 node가 없을 경우, **null**이 저장
* head node → second node → third node를 알아내는 식으로 마지막 node까지 접근. 따라서 특정 node에 접근하고 싶다면 head node부터 시작
* 삽입과 제거를 쉽게 할 수 있다

**연결리스트 vs 배열**

| 종류    | 크기 | 참조성능 | 수정성능 | 공간복잡도 | 시간복잡도 |
| ----- | -- | ---- | ---- | ----- | ----- |
| 배열    | 정적 | 좋음   | 안 좋음 | 좋음    | O(1)  |
| 연결리스트 | 동적 | 안 좋음 | 좋음   | 안 좋음  | O(n)  |

* **배열**은 10층으로 바로 갈 수 있는 엘리베이터
* **연결리스트**는 10층까지 순서대로 걸어 올라가야 한다.

***

#### 연결리스트 메서드 활용

`**push` 메서드\*\*

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(val) {
    let newNode = new Node(val);
    // head가 없다면 새로운 node를 head, tail로 할당
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
      // head가 있다면 새 node를 tail의 다음 list로 할당
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    // list의 length
    this.length += 1;
    return this;
  }
}

const list = new SinglyLinkedList();

// list.push(1)
// > SinglyLinkedList {head: Node, tail: Node, length: 1}

// list.head
// > Node {val: 1, next: null}

// list.tail
// > Node {val: 1, next: null}

// list.push(10)
// > SinglyLinkedList {head: Node, tail: Node, length: 2}

// list.tail
// > Node {val: 10, next: null}

// list.head.next
// > Node {val: 10, next: null}

// 현재 list는 1 - 10 의 형태
```

**`pop` 메서드**

```jsx
pop() {
    if (!this.head) return undefined;
    let current = this.head;
    let newTail = current;
    // 현재 node의 next node가 있을 때까지 반복
    while (current.next) {
      // 다음 node가 있다면
      // 현재 node를 newTail로 할당
      newTail = current;
      // 현재 node의 next를 현재 node로 할당
      current = current.next;
    }
    // 다음 node가 없다면 newTail을 this.tail에 할당
    this.tail = newTail;
    // this.tail의 다음 node를 null로 설정함으로써
    // 1. 이후에 아무것도 없다고 알려주고
    // 2. '!'에 대한 연결을 끊는다
    this.tail.next = null;
    this.length--;

    // head만 남은 상황에서 pop 메서드를 사용하면 head, tail 모두 null
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return current;
  }

// pop 메서드

// list.pop()
// > Node {val: '!', next: null}

// list.pop()
// > Node {val: 'goodbye', next: null}

// list.pop()
// > Node {val: 'hello', next: null}

// list.pop() undefined
```

**`shift` 메서드**

```jsx
shift() {
    // head가 없으면 return
    if (!this.head) return undefined;
    // 현재 head를 currentHead로 할당
    let currentHead = this.head;
    // currentHead의 다음 node를
    this.head = currentHead.next;
    this.length--;

		if (this.length === 0) {
      this.tail = null;
    }
    return currentHead;
  }

// shift 메서드
// list.shift()
// Node {val: 'hello', next: Node}

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 2}head: Node {val: 'goodbye', next: Node}length: 2tail: Node {val: '!', next: null}[[Prototype]]: Object

// list.shift()
// > Node {val: 'goodbye', next: Node}

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 1}
```

**`unshift` 메서드**

```jsx
unshift(val) {
    // 새로운 node 생성
    let newNode = new Node(val);
    // head가 없으면 새 node를 head에 할당, 기존 head를 tail에 할당
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    }
    // 현재 head를 새 node의 다음 node로 할당
    newNode.next = this.head;
    // 그리고 새 node를 현재 head로 할당
    this.head = newNode;
    this.length++;
    // 전체 list return
    return this;
  }

// unshift 메서드
// list.unshift('first')
// > SinglyLinkedList {head: Node, tail: Node, length: 4}
//   head: Node {val: 'first', next: Node}
//   length: 4
//   tail: Node {val: '!', next: null}
```

**`get` 메서드**

```jsx
get(index) {
    // index가 0보다 작고 또는 list 길이보다 크거나 같으면 null
    if (index < 0 || index >= this.length) return null;
    let counter = 0;
    // list의 head를 current값으로 할당
    let current = this.head;
    // counter가 index값과 같지 않을때까지 '현재 node의 다음 node'를 current node에 할당하며 반복
    while (counter !== index) {
      current = current.next;
      counter++;
    }
    return current;
  }

// get 메서드
// list.get(-2)
// > null

// list.get(6)
// > null

// list.get(3)
// > Node {val: 'what', next: Node}
```

**`set` 메서드**

```jsx
set(index, val) {
    // get 메서드로 index를 찾고 foundNode에 할당
    let foundNode = this.get(index);
    // foundNode가 있으면 val값을 foundNode의 val값에 저장하고 true 반환 그렇지 않으면 false반환
    if (foundNode) {
      foundNode.val = val;
      return true;
    }
    return false;
  }

// set 메서드
// list.get(3)
// > Node {val: 'what', next: Node}

// list.set(3, 'oh')
// > true

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 5}head: Node {val: 'hello', next: Node}length: 5tail: Node {val: 'the', next: null}[[Prototype]]: Object

// list.get(3)
// > Node {val: 'oh', next: Node}

// list.set(6, 'asdasd')
// > false
```

`**insert` 메서드\*\*

```jsx
insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return this.push(val);
    if (index === 0) return this.unshift(val);

    let newNode = new Node(val);
    let prev = this.get(index - 1);
    let temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }
// 1. 입력한 index가 0보다 작거나 list 길이보다 크면 false
// 2. 입력한 index가 list의 길이와 같으면 list 끝에 새로운 node를 추가한다
// 3. 입력한 index가 0이면 새로운 node(val)를 list의 맨 앞에 unshift한다

// 4. 입력한 값의 node(val)를 newNode 변수에 할당한다
// 5. insert하려는 index를 찾기 위해서 get 메서드를 사용해 index - 1 값의 node를 prev 변수에 할당한다
// 6. val를 담을 node(prev.next)를 temp에 할당한다
// 7. 이 temp node를 새로 생성한 node의 next에 할당한다

const list = new SinglyLinkedList();

list.push(100);
list.push(201);
list.push(250);
list.push(350);

// insert
// list.insert(0, 'first');
// > SinglyLinkedList {head: Node, tail: Node, length: 5}

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 5}head: Node {val: 'first', next: Node}length: 5tail: Node {val: 350, next: null}

// list.get(4)
// > Node {val: 350, next: null}

// list.insert(5, 'last')
// > SinglyLinkedList {head: Node, tail: Node, length: 6}head: Node {val: 'first', next: Node}length: 6tail: Node {val: 'last', next: null}

// list
// > SinglyLinkedList {head: Node, tail: Node, length: 6}head: Node {val: 'first', next: Node}length: 6tail: Node {val: 'last', next: null}

// list.get(5)
// > Node {val: 'last', next: null}
```

**`remove` 메서드**

특정 index의 node를 제거

```jsx
remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    let prev = this.get(index - 1);
    let removed = prev.next;
    prev.next = removed.next;
    this.length--;
    return removed;
  }
// 1. 입력한 index값이 0보다 작거나 list 길이보다 크면 undefined
// 2. 입력한 index값이 0이면 shift메서드를 사용해 제거
// 3. 입력한 index값이 tail이면 pop메서드 사용해 제거

// 4. get메서드를 사용해 제거하려는 index 전의 node를 prev에 할당
// 5. prev의 다음 node를 removed(제거할) 변수에 할당
// 6. removed(제거할) node의 다음 node를 prev의 다음 node에 할당

// remove 메서드
// list.remove(0)
// > Node {val: 100, next: Node}

// list.remove(2)
// > Node {val: 350, next: null}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://adam-37.gitbook.io/joomadeung/undefined-2/undefined/undefined-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.