[자료구조] LinkedList 란?

데이터를 집어넣는 방법

메모리 확보 후 연속된 공간에 채워넣기 vs 필요할 때마다 메모리를 할당받아 데이터를 저장
전자는 배열이고 후자는 연결리스트 즉, Linked List 라고 함

배열과 링크드 리스트의 차이

배열의 특징 : 미리 공간을 확보하지만, 확보되는 공간보다 적게 사용하면 메모리가 낭비될 수 있음
cf. 배열의 한 칸을 셀(cell), 또는 요소(element)라고 함
링크드 리스트 특징 : 낭비되는 데이터는 없지만, 연관 데이터끼리 '연결' 짓는게 필요함
node는 필요에 따라 동적으로 할당되고 자바에서는 자동으로 메모리를 정리해주므로 낭비되는 저장 공긴이 없음
하지만 data와 idx만 저장하는 배열과 달리 추가적으로 저장해야 될 것이 있으므로 그 자체의 저장 공간은 배열보다 큰 편

링크드 리스트란?

링크드리스트는 두개의 필드로 이루어진 node가 기본 단위이다.
node는 데이터를 저장하는 데이터필드와 다음 노드를 가리키는 링크필드로 구성된다.
node는 서로 다른 데이터타입을 하나로 묶으므로 class에 해당된다.
e.g class Node { int data; Node next; }

연결 리스트의 종류로는 단일 연결리스트 (Singly Linked List), 이중 연결리스트 (Doubly Linked List),
원형 연결리스트가 있다.
단일 연결 리스트는 head ⇒ tail 의 방향으로 다음 노드의 주소만 갖지만,
이중 연결 리스트는 head <=> tail 의 방향으로 이전과 다음 노드의 주소를 모두 갖는다.
원형 연결 리스트는 이중 연결 리스트이면서, head와 tail이 연결되어있다. 

데이터에 접근하는 방법

배열의 데이터에 접근하는 방법 :
배열은 배열의 주소와 인덱스만 알면 바로 접근 가능함.
첫번째 셀의 주소 + (데이터타입의 크기 * 해당 데이터의 인덱스)
ex. int 배열의 주소가 400일때 세번째 셀의 주소는 400 + 4*2 = 408
⇒ 배열은 데이터에 대한 접근이 쉽고 빠르다.

링크드 리스트의 데이터에 접근하는 방법 :
링크드 리스트는 배열처럼 메모리공간에 정렬되어있지 않고 사방에 흩어져 존재한다.
따라서 배열처럼 특정 노드의 공간을 바로 계산할 수 없다.
ex. 1~10번 노드가 있는데 4번노드에 접근하려고하면 1번부터 4번까지 탐색해야만 한다.
링크드 리스트는 무조건 헤드에서 시작해야 한다.