연결 자료구조 | Linked List | 連結リスト（１）

할로윈을 맞이하야 그런 느낌으로 꾸며봄 👻🎃
참고 도서 : C로 배우는 쉬운 자료구조, 근데 내가 사용하는 건 2007년 책 -> C언어를 내 포스트에서 다루지는 않을 것. 이거는 지난 학기에 급하게 중고로 구한거라..

선형 리스트는 어떤 문제를 가지고 있을까?

• 삽입이나 삭제 후 연속적인 물리 주소를 유지하기 위해 원소들을 이동시키는 추가 작업과 시간이 소요
• 배열을 이용하여 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제가 발생

문제를 개선한 자료 표현 방법 -> 연결 자료구조

• 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식
• 물리적인 순서를 맞추기 위한 오버헤드가 발생 X
• 여러개의 작은 공간을 연결하여 전체를 표현하기에 크기 변경이 유연하고 좀더 효율적으로 메모리를 사용할 수 있음

노드

• 연결 자료구조에서 원소는 연결될 다음 원소에 대한 주소를 저장해야함
• <data field, link field> 단위로 저장 -> 이를 Node라고 함

• week는 연결 리스트의 시작을 가리키는 포인터 변수
• 연결 리스트의 마지막 노드는 다음에 연결되는 노드가 없으므로 링크 필드에 저장할 값이 없기에 NULL

How To Create A Node With Javascript

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

How To Create A Node With Java

public class creatNodes {    
    class Node{    
        int data;    
        Node next;    
            
        public Node(int data) {    
            this.data = data;    
            this.next = null;    
        }    
    }
}