linked list 연결 리스트에 대하여

연결 리스트가 어디에 쓰이는데 ?

웹 브라우저의 history를 관리할 때 사용.. 웹 브라우저 상에서 여러 사이트들을 돌아다니게 되면, 방문 history에 방문 기록들이 연결 리스트와 같은 구조로 저장.
이와 같은 방법으로 브라우저에서 뒤로 가기, 앞으로 가기 버튼을 누르게 되면 열람했던 사이트 들로 이동할 수 있게 되는 것이다.

그렇다면 연결리스트 그게 뭔데..
알아보도록 하자 레츠 고

연결 리스트(Linked List) 란?

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

각 노드는 다음 노드를 가리키는 포인터(다음 노드의 주소)를 포함한다.

각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가진다.
각 포인터 변수의 주소 또한 가지고 있음.

맨 앞을 Head라고 하며, null을 참조하고 있는 맨 마지막 값을 Tail 이라고 부른다.

연결 리스트(Linked List)의 종류

이 때까지 설명한 건 제일 기본적인 단방향 연결 리스트였고..
종류가 몇가지 더 있다.

1. Doubly Linked List (이중 연결 리스트)

연결 리스트에서 탐색 할때, 뒤쪽 원소를 검색하면
loop를 처음부터 싹 돌아야 하기 때문에 탐색 속도가 느리다..

이 문제를 해결하려면 뒤쪽 원소들도 빠르게 검색할 수 있게
이중 연결 리스트 구조를 활용!

주소지가 2개(앞뒤) 저장되므로 저장공간이 추가로 더 필요하다는 단점 존재...

2. Circular Linked List(원형 연결 리스트)

연결 리스트는 항상 앞에서만 탐색을 수행하게 된다.
만약 이중 연결 리스트 구조를 적용하더라도 앞 또는 뒤에서만 탐색을 할 수 있게 되는데...
이 문제를 해결하기 위해서 !!!

앞과 뒤과 연결되어 있고 마지막 작업 위치를 Head이자 Tail로 설정된 Circular Linked List (원형 연결 리스트) 구조가 있다!

이 원형 리스트를 사용하게 되면
Head가 어딘지.. Tail이 어딘지 신경 쓸 필요가 없게 된다.
마지막 작업하던 위치에서 이어서 탐색, 삽입, 삭제 등의 연산을 바로 수행할 수 있게 된다는 장점이 있다.

하지만.. 데이터 순서의 개념이 모호해지고, 인덱스를 사용한 탐색이 어려워지게 된다.. 단점 !