자료구조(java) 3_1. 연결 리스트 소개 (copy)

연결 리스트(Linked List) 소개

연결 리스트는 항상 맞는 크기로 만들어지도록 설계되어 있다.

순차적인 데이터나 많은 양의 데이터가 있을 때 특히 자주 사용된다.

연결 리스트 vs 배열

배열 또한 순서대로 여러 데이터를 저장할 때 사용한다는 공통점이 있다.

하지만 배열은 필요한 요소보다 너무 크게 만들거나 너무 작게 만들어 배열의 크기를 조정해야 한다는 문제점이 있다.

배열과 다르게, 연결 리스트는 항상 맞는 크기로 만들어지도록 설계되어 있다.

그래서 순차적인 데이터나 많은 양의 데이터가 있을 때 자주 사용됩니다.

노드(node)

연결 리스트의 기본 구성요소

노드에는 두가지 정보가 들어있다.

• next라는 이름의 ‘포인터’
• 우리가 노드에 넣은 어떠한 ‘데이터’

📍 각각의 포인터는 인접한 노드를 가리키게 된다. (그렇기 때문에 포인터의 이름이 next)

📍 자신 노드 다음에 오는 노드가 없다면 null을 가리킨다.

❗ 포인터는 어떤 공간을 가리킨다.

❗ 그리고 사실 data도 어떤 요소를 가리키는 포인터이다.(우선은 어떤 객체를 가리키는 변수라고 생각하자.)

이 리스트는 head라는 이름의 포인터에서 시작한다.

✅이 연결리스트에 접근할 수 있는 유일한 방법은 Head.

힙에서 우리는 Head의 위치만을 알고 있고,

우리는 힙에서 Head 노드를 가리키는 포인터를 가지고 있는 것.

node A는 head.next로 표현할 수 있고, B는 head.next.next, C는 head.next.next….

이렇게 .next로 이어가기엔 좋지 않음.

👉 임시 포인터를 통해 연결리스트의 첫 부분에서 시작해서 각각의 노드를 따라서 탐색하는 방법을 사용.

(임시 포인터 사용하여 탐색하는 방법은 다음 강의)

생각해보기

\1) 일상생활에서 연결 리스트처럼 여러 물건을 연결하여 정리하는 것에는 어떤 것이 있나요?

네비게이션 지도가 링크드 리스트의 예라고 할 수 있다.

혹은 폴더 구조, 인터넷 주소 탐색 등에도 쓰일 수 있다.

https://medium.com/swlh/real-life-example-of-a-linked-list-8f787b660b3f

References

자바로 구현하고 배우는 자료구조 -Rob Edwards (boostcourse)