연결리스트(Linked List)

연결리스트

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

 

출처  : https://winplz.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List

 

연결리스트는 여러 노드들이 연결되어 있는 구조입니다.

여기서 노드란, data와 next를 가지고 있는 구조입니다. (Data, Next 가 같이 묶여 있는 것이 Node)

연결 리스트의 구조에서 맨 앞을 Head라고 하고 맨 마지막을 Tail이라고 합니다. 

 

단방향 연결리스트

: 한쪽 방향으로만 연결된 링크드 리스트

자료 생성시, 노드가 생성되고 포인터는 생선된 포인터를 가르킨다.

 

양방향 or 쌍방향 연결리스트

: 양쪽 방향으로 연결된 쌍방향 링크드 리스트

자료 생성시, 노드가 생성되고 전 노드의 포인터는 생성된 포인터를 가르킨다.

그리고 생성된 노드의 Prev 포인터는 전 노드를 가르킨다.

 

환형 연결리스트

: 고리의 처음과 끝이 함께 연결되어 있는 링크드 리스트

양방향과 같지만, 마지막 노드의 Next 포인터는 처음을 가리키는 부분이 추가된다.

 

연결리스트의 쓰임새

이런 연결 리스트는 웹 브라우저의 히스토리를 관리할 때 사용됩니다. 

예를들어 브라우저에서 뒤로가기, 앞으로가기를 할 때 히스토리의 방문기록을 가지고 있기 때문에 손쉽게 이동이 가능합니다.

 

배열과 연결리스트의 차이

	장점	단점
배열	- 랜덤 엑세스가 빠르다 (매우 빠르게 접근 가능)	- 메모리 사용 비효율적 - 배열 내의 데이터 이동 및 재구성이 어렵다
연결리스트	- 동적으로 메모리 사용가능 - 메모리 효율적 사용 -  데이터 재구성 용이 - 대용량 데이터 처리 적합	- 특정위치 데이터 검색 할 때 느리다 - 메모리를 추가적으로 사용해야한다

 

참고 

https://overcome-the-limits.tistory.com/16

https://winplz.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List