linkedlist

링크드 - 연결이라는 말.
데이터 스트럭쳐의 미션은 메모리의 효율적 사용이다.
각각의 주소에 접근하는 시간이 동일. RAM

Linked List vs Array List

Array List - 각각의 엘리먼트가 연속적'으로 붙어있다. 크기를 항상 알고 있어야한다.
Linked List - 각각의 엘리먼트가 흩어져 있으나 그러나 다 연결되어 있다. 가변길이이며 크기를 설정하지 않는다.

Linked List(연결 리스트)

그 크기가 동적인 자료구조이며 여러 개의 노드로 이루어져 있다. 각각의 노드는 데이터와 다음 노드가 뭔지 알려주는 주소를 가지고 있다. 또한 Linked List는 새로운 데이터를 추가하거나, 데이터의 위치를 찾거나, 제거하는 기능이 있어야 한다.

Linked List의 시간 복잡도

• 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우 O(1) (상수 시간)의 시간복잡도를 가진다.
• 다만 추가와 삭제 속도에 대한 대가로, Linked List의 각 노드는 인덱스를 갖지 않는다. 어떤 특정 데이터를 Linked List에서 검색하고자 할 경우, 처음부터 전체 Linked List를 훓어야 하며, 이는 O(n) (선형 시간)의 복잡도를 필요로 한다.
  

Linked List의 종류

Singly Linked List

• 노드 안에 링크가 1개이고 단방향으로 진행하는 리스트, 다음 주소만 가짐.
  

Doubly Linked List

• 노드 안에 링크가 2개이고 양방향으로 진행 할수 있는 리스트, 내 앞이 어딘지 추가로 주소를 가지고 있다.
  

Circular Linked List

• 마지막 노드가 첫번째 노드를 가르켜서 계속 회전 할 수 있게 만들어진 리스트
  

Linked List의 실제 사례 :

1) Singly Linked List

1.아이의 인간 두뇌 (예를 들어 시를 기억하기 위해서는 연결 해야 합니다. 마지막 줄을 물어보면 첫 줄부터 읽어야합니다)
2.네트워크에서 메시지 전달 (메시지는 패킷으로 나뉘고 각 패킷에는 다음 키가 있으므로 수신자 쪽에서 쉽게 클럽을 만들 수 있음)

2) Doubly Linked List

1.DNA 분자
2.뒤로 버튼을 사용할 수있는 브라우저 캐시.
3.자전거의 롤러 체인 (doubly circular linked list)
4.열차 객차는 다음 및 이전 객차와 연결된다.

3) Circular Linked List

1.에스컬레이터
2.운영 체제에서 프로세스를 스케줄링하는 동안 스케줄러가 사용하는 시간 공유 문제.