[자료구조] 연결리스트, 배열과의 차이점

1. 연결리스트의 등장 _ 배열의 단점을 극복하자

- 배열의 단점 : 크기를 예측하기 힘들어 메모리 낭비 발생

- 데이터 삽입, 삭제가 비효율적

2. 연결 리스트

작동원리

분산데이터를 연결시켜 줄 노드가 존재한다.

노드는 데이터를 담는 변수, 다음 노드를 가르키는 변수를 가지고 있다.

데이터가 필요하면 필요한 데이터만큼 노드를 만들어 데이터를 저장하고 다음 노드를 가리켜 저장한다.

연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 가능하다.

장점

연결리스트로 데이터를 추가하면 빈 메모리공간 아무 곳에 데이터를 생성하고 연결만 해주면 된다.

3. 배열 VS 연결리스트

배열과 비교 했을때 연결리스트의 장점

배열은 중간에 데이터 삽입시 정해진 메모리 공간을 초과하여 오버헤드가 발생한다.

연결 리스트는 불연속공간에 데이터 저장을 하고 다음 가르키는 노드만 바꿔주면 된다.

배열과 비교 했을때 연결리스트의 단점

배열은 데이터가 연속적으로 저장되어있기 때문에 첫번째 데이터 주소만 안다면 다른 데이터도 찾을 수 있다.

연결 리스트는 첫번째 노드에서 다음 노드를 찾는 과정을 반복하여 데이터를 찾아야 한다.

O(N) 성능을 가진다.

4. 적재적소

참조를 할때는 배열
데이터의 크기가 자주 바뀐다면 연결 리스트

5.연결리스트 구현

test.mjs 작성

    class Node{
    //노드만들어주기
     
    
        constructor(data, next = null){
            //클래스를 인스턴스화 했을 때 자동으로 호출 되는 생성자
            this.data = data;
            this.next = next;
        }

    }
    export { Node };

LinkedLIst.mjs 작성

    import {Node} from 'C:\Users\PC\Desktop\javascript\.vscode\BootCamp\javascript\js\LinkedList.js'; //node 클래스를 사용 가능

    let node1 = new Node(1);
    let node2 = new Node(2);
    let node3 = new Node(3);

    node1.next = node2;
    node2.next = node3;

    console.log (node1.data);
    console.log (node1.next.data);
    console.log (node1.next.next.data);