자료구조(3)_Linked List

Linked List ? 

- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조 . 

- 이름과 같이 노드의 포인터가 다음이나 노드와의 연결을 담당하게 된다. 

- 리스트는 노드와 노드가 서로 연결된 형태로 되어있다. 

- 각 노드는 데이터의 내용을 담는 부분과 다음 노드의 주소값을 갖는 포인터 변수로 구성되어 있다.

- 시작(주소) ->연결(Link) -> 끝(Null Point) 이 순서이다.

- Linked List는 여러개의 Node를 연결함으로써 데이터를 표현한다.

- 배열(Array)와 유사하지만 훨씬 효율적인 저장 방법이다.

 

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

세 개의 정수를 저장하고 있는 단순 연결 리스트(Linked List)

- 리스트의 첫번째 노드를 Head, 마지막 노드를 Tail이라 한다. 

- Linked List 의 종류에는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 가 있다. 

- 단일 연결 리스트는 next로 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로는 갈 수 없다. 

- 이런 단점을 해결하기 위해 노드 앞 메모리 주소를 보관하는 포인터(prev)를 만들어준 형태인 이중 연결 리스트(Doubly Linked List)가 있다. 

 

노드 앞 포인터가 특징인 이중 연결 리스트(Doubly Linked List)

- 단순 연결 리스트(Linked List)의 마지막 노드의 포인터가 NULL이 아닌 Head를 가리키는 형태의 리스트인 원형 연결 리스트(Circular Singly Linked List)도 있다. 

마지막 노드 포인터가 NULL이 아닌 Head를 가리키는 원형 연결 리스트(Circular Singly Linked List)

- 마지막 노드의 포인터가 NULL이 아닌 , Head를 가리키기 때문에 이 리스트의 끝이 존재하지 않는것이 특징이다.