LinkedList (연결리스트)

연결리스트?

• 포인터를 사용해서 데이터(아이템)들이 메모리공간에 연속적으로 있지 않아도 되는 자료구조.
• 데이터들은 포인터를 통해 데이터 i를 인접항목 i+1과 연결하여 인덱스 0 ~ N-1까지 정렬된다. -> 저장장치에 물리적으로 한 줄로 세우는 것이 불필요.
• 연결리스트는 노드로 이루어져 있는데, 노드는 데이터, 포인터로 구성된다.
• head pointer는 a0를 가리킨다. tail pointer는 a(N-1)을 가리킨다(tail item 이후에는 아무것도 없다.)

연결리스트

연결리스트의 동작과 시간복잡도

• 검색 : head에서부터 원하는 노드가 나올 때 까지 검색. O(N)
• 추가 : 추가동작만 한다면 O(1). 검색과 추가를 합친다면 O(N).
• 제거 : 제거동작만 한다면 O(1). 검색과 제거를 합친다면 O(N).

연결리스트와 배열의 차이점

linkedlist vs array

	연결리스트	배열
검색	순차검색 O(N)	random accecss O(1)
저장방식	메모리의 어딘가	배열이 저장되어 있는 메모리 바로 뒤
추가/삭제	O(1) (검색 제외)	메모리에 연속적으로 고정되어 있으므로 오래걸린다
memory allocation	Dynamic	Static
크기	자유로움.	배열이 선언될 때 정해짐
memory allocated  section	Heap	Stack

구현 시 어려웠던 점

• 새로 생성되는 노드들에 전부 이름을 붙여줘야한다고 생각하였다. (node1, node2... 와 같이) 그 생성된 노드들의 이름을 각각 써서 연결시켜야한다고 생각했다. 그러나 linkedlist는 head에서부터 순차적으로 하나의 노드가 다음 노드를 가리키게 된다. 이를 연속적으로 수행하게 되면 생성자함수로 생성한 노드를 next에 지정만 해줌으로써 그 노드들을 저장할 수 있게 된다.
• 처음 생각한 linkedlist 객체
  list = {head: {value: , next: node1}, node1: {value:, next: node2}, node2: {}, node3: {}, ... tail: {value, null}}
• next를 이용해서 구상한 linkedlist 객체
  list = {head: {value: , next: {value: next: {value: next: {value: next: }}}, tail: {value, next: null}}