자료구조 - LinkedList

Linked List는 Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것이다.

Linked list에서 가장 중요한 것은 연결이 무엇인가를 파악하는 것이다.

linked list는 한 건물 내에서 한 회사가 임대한 사무실이 사진처럼 서로 떨어져 있다.
덕분에 직원이 늘어도 큰 걱정이 없습니다. 건물에서 비어있는 곳 아무데나 임대해서 들어가면 되니까.
그런데 방문자가 사무실을 찾는 방법이 비효율적이다.
위의 그림에 있는 방문자가 3번째 사무실을 찾아가려면 우선 첫 번째 화살표의 사무실을 찾아가야 한다.
이 사무실의 직원에게 다음 사무실이 어딘지 물어본다.
그럼 알려주는 사무실로 이동 한 후에 다시 물어봐서 그다음 사무실로 이동한다.

이렇게 물어물어 사무실을 찾아가야 하는 방식이 LinkedList 이며, 검색이 느리다.

ArrayList는 해당 위치의 주소만 알면 바로 찾아가면 되므로 검색이 빠르다.

그렇다면, LinkedList를 쓰면 장점이 어떤게 있을까?

• 삽입과 삭제가 용이 : 포인터로 연결되어 있어서 가리키는 노드만 변경해주면 됨
• 크기가 가변적 : 새로운 원소 추가 시 동적으로 크기가 변경된다.
• 불연속적 메모리 할당 : 빈 공간 없이 데이터를 저장할 수 있다. ( ex. 중간 데이터 삭제 시)
• 사용한 메모리를 재사용할 수 있다

LinkedList는 내부적으로 Element라는 용어 대신 node 또는 vertex라는 용어를 사용한다.

https://visualgo.net/en/list

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

위 사이트에서 Linked List의 자세한 방법을 알 수 있다.