2019.09.18 Linked List

Linked List

이해하기 어렵다.......면?

코드로 먼저 어떻게 생겼는지 보자

Array:          0: 12    1: 99    2: 37
Linked List:    head → 12 → 99 → 37 → ∅

const list = {
    head: {
        value: 12
        next: {
            value: 99
            next: {
                value: 37
                next: null
            }
        }
    }
};

느낌이 head로 시작해서 value가 있고 next로 데이터들이 연결되는 느낌
그리고 마지막의 tail의 값은 null이 되면 될 것 같은 느낌

1. 각 노드가 데이터와 포인터(next)를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

2. 한정된 메모리에서 자유로운 공간에 데이터 저장이 가능메모리의 효율적 사용 가능

데이터를 저장하고 이전 데이터와 다음 데이터를 연결만 해주면 되기 때문에
메모리의 공간 사용이 용이하다.
아래의 그림을 참조하면 바로 이해가 될 것 같다.

3. Linked List에서 사용되는 용어 (예상)

• node : 한개의 데이터 set으로 value, next(default : null)의 값이 있는 객체
• addToTail : 새로운 데이터를 리스트의 가장 끝에 붙인다.
• removeHead : 헤드를 삭제하는 기능 (두 번째 데이터를 헤드로 전환 시켜주는 과정 필요)
• removeValue : 데이터를 삭제 (앞의 데이터와 뒤에 붙는 데이터를 연결해주는 과정이 필요)
• hasValue : 데이터의 유무를 파악 (index가 없기 때문에 head부터 뒤져서 있으면 true, 없으면 false)

(List)

1. (List) Linked List default 리스트 생성

   function List (데이터) {
     // this.head = null;
     // this.tail = null; 필요시 tail 이 무엇인지도 바로 확인 가능) 
   }
   // 기본 

(node)

2. (node) Linked List의 데이터 단위인 노드 생성

   function Node (데이터) {
     // this.value = 데이터
     // this.next = null; 
   }
   let myNode = new Node(데이터이름) // 노드의 클래스를 만들고 인스턴스를 생성

(addToTail)

2. (addToTail) 리스트의 가장 끝에 데이터를 추가

   List.addToTail = function(데이터) {
    // if (리스트에 노드가 없으면) head에 첫 노드를 추가
    // else 꼬리에 노드 추가
   }

(removeHead)

3. (removeHead) 리스트의 헤드를 삭제

   List.removeHead = function() {
    // head를 삭제
    // head에 연결되어 있는 두 번째 노드를 head로 변경
   }

(removeValue)

4. (removeValue) 리스트에 있는 데이터를 삭제

   List.removeValue = function(데이터) {
    // 리스트의 next를 따라가면서 데이터가 있는지 확인
    // 있으면 삭제
    // 삭제 후 데이터 전 후의 데이터를 연결해주는 작업 필요
   }

(hasValue)

5. (hasValue) 리스트에 데이터가 있는지 확인

   List.hasValue = function(데이터) {
     // 리스트의 head 부터 차례대로 돌면서 데이터가 있는지 확인
     // 리스트의 경우 index가 없기 때문에 head부터 돌아야 함
     // 있으면 true, 없으면 false 반환
   }

마지막으로 Array List vs Linked List

1. Array List

첫번째 회사는 모든 직원이 한곳에 모여있어야 한다는 철학이 있기 때문에 사무실이 모여있습니다. 배열은 건물을 이런 식으로 사용하는 것과 비슷합니다. 만약 회사가 성장해서 사무실이 좁아지면 더 이상 새로운 직원을 뽑을 수 없습니다. 붙어있는 공간이 없기 때문이죠. 만약 더 많은 공간이 필요하다면 더 많은 사람을 수용할 수 있는 공간을 찾아서 전체가 이사해야 합니다.

2. Linked List

linked list는 한 건물 내에서 한 회사가 임대한 사무실이 서로 떨어져 있습니다. 덕분에 직원이 늘어도 큰 걱정이 없습니다. 건물에서 비어있는 곳 아무데나 임대해서 들어가면 되니까요. 그런데 방문자가 사무실을 찾는 방법이 좀 비효율적입니다. 위의 그림에 있는 방문자가 3번째 사무실을 찾아가려면 우선 첫 번째 화살표의 사무실을 찾아가야 합니다. 이 사무실의 직원에게 다음 사무실이 어딘지 물어봅니다. 그럼 알려주는 사무실로 이동 한 후에 다시 물어봐서 그다음 사무실로 이동합니다.

이렇게 물어물어 사무실을 찾아가야 하는 방식이 linked list입니다. 그래서 linked list에서는 몇 번째 엘리먼트를 찾는 것이 느립니다.

반면에 array list는 엘리먼트가 같은 곳에 모여있습니다. 만약에 3번째 자리로 가고 싶다면 한번에 3번째 방으로 갈 수 있습니다. 찾고자 하는 사무실이 몇 번째에 있는지 알고 있다면 ArrayList는 매우 빠릅니다.

• by. 생활코딩 https://opentutorials.org/module/1335/8821