자료구조(3)_Linked List
Linked List ?
- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조 .
- 이름과 같이 노드의 포인터가 다음이나 노드와의 연결을 담당하게 된다.
- 리스트는 노드와 노드가 서로 연결된 형태로 되어있다.
- 각 노드는 데이터의 내용을 담는 부분과 다음 노드의 주소값을 갖는 포인터 변수로 구성되어 있다.
- 시작(주소) ->연결(Link) -> 끝(Null Point) 이 순서이다.
- Linked List는 여러개의 Node를 연결함으로써 데이터를 표현한다.
- 배열(Array)와 유사하지만 훨씬 효율적인 저장 방법이다.
- 리스트의 첫번째 노드를 Head, 마지막 노드를 Tail이라 한다.
- Linked List 의 종류에는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 가 있다.
- 단일 연결 리스트는 next로 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로는 갈 수 없다.
- 이런 단점을 해결하기 위해 노드 앞 메모리 주소를 보관하는 포인터(prev)를 만들어준 형태인 이중 연결 리스트(Doubly Linked List)가 있다.
- 단순 연결 리스트(Linked List)의 마지막 노드의 포인터가 NULL이 아닌 Head를 가리키는 형태의 리스트인 원형 연결 리스트(Circular Singly Linked List)도 있다.
- 마지막 노드의 포인터가 NULL이 아닌 , Head를 가리키기 때문에 이 리스트의 끝이 존재하지 않는것이 특징이다.