배열이 연속된 메모리에 저장하고, 인덱스를 사용한 자료구조라면
연결리스트는 떨어진 메모리에 저장한 뒤 링크를 사용한 자료구조라고 할 수 있다.
인덱스를 사용하기에 Arr[1] 와 같은 명령으로 검색에 O(1)의 복잡도가 드는 배열과 달리
Head에서부터 차례대로 검색해야하는 연결리스트의 검색 복잡도는 O(n)이다.
연결리스트의 종류
1. 단순 연결리스트 : Node 1개에 링크 1개가 있다.
2. 이중 연결리스트 : Node 1개에 링크 2개가 있다. (이전 Node 링크 1개, 이후 Node 링크 1개)
3. 원형 연결리스트 : 마지막 Node(tail)의 링크가 첫 Node(head)를 가리킨다.
4. 이중 원형 연결리스트 : 이중 + 원형의 연결리스트
연결리스트의 종류
1. 단순 연결리스트 :Node 1개에 링크 1개가 있다.
2. 이중 연결리스트: Node 1개에링크 2개가 있다. (이전 Node 링크1개,이후 Node 링크1개)
3. 원형 연결리스트 : 마지막 Node(tail)의링크가첫 Node(head)를 가리킨다.
4. 이중 원형 연결리스트 : 이중+원형의 연결리스트