[자료구조] LinkedList 기본 개념

okoo 2021. 10. 24. 13:49

안녕하세요 공부하는 개발자입니다.

개발자는 정말 어려운 길입니다. 공부를 해야 할 분야도 엄청 넓고 언어도 다양해지면서 점점 더 공부해야 할 것들이 늘어나고 있습니다.

하지만 개발자라면 모두들 공부하는 자료구조와 알고리즘에 대해서 공부를 시작해 보려 합니다.

오늘은 LinkedList입니다.

아마 자료구조와 알고리즘 책을 보면 가장먼저 보게 될 자료구조 중 하나입니다.

주로 다음에 공부할 배열과 비교가 많이 되는 자료구조라 할 수 있습니다.

이 Linked List는 흩어진 상태로 메모리에 저장을 시킵니다.

이 부분이 배열가 가장 큰 차이를 만들어내는 부분입니다.

이러한 데이터를 담는 것을 노드라고 하는데

A가 데이터 Next에는 다음 노드로가는 주소를 담는 구조로 노드가 만들어져 있습니다.

Linked-List의 경우 삭제나 추가가 쉽습니다.

배열처럼 묶여있는 것이 아니라 노드에서 주소를 가지고 있어 주소만 바꿔주면 간편하게 데이터를 추가 할 수 있습니다.

만약 데이터가 삭제 된다면 삭제된 데이터의 경우 메모리에서 삭제되었다고 표시를 해야하지만 Java의 경우 가비지 컬렉터의

도움으로 무시하고 진행을 해도 무방하다

그림과 같이 노드가 한 방향으로 이어져있는 것을 단방향 연결 리스트라고 합니다.

이러한 단방향 연결 리스트의 경우에는 공간의 효율은 좋으나

데이터의 검색 시 알맞은 데이터가 검색되기 전까지 A데이터부터 찾아야 한다는 단점이 있습니다.

예를 들어 'C'라는 데이터를 검색하고 싶다면 A -> B -> C로 순차적으로 검색을 해야 하는 경우입니다.

반대로 양방향 연결 리스트 또한 있습니다.

Before

이러한 노드를 가지고 있습니다.

Before에는 이전 노드의 주소를 A에는 데이터 Next에는 다음 노드의 주소를 가지고 있어 양방향으로 데이터 이동이 가능합니다.

장점이라면 단방향의 단점인 검색을 빠르게 해 준다는 장점이 있습니다.

하지만 단점 또한 단방향과 반대로 노드가 크기 때문에 공간 효율성이라는 측면에서는 단방향보다 떨어집니다.

단방향이든 양방향이든 우리가 사용하는 알고리즘에 따라서 선택하여 사용하면 깔끔한 코드에 가까워질 수 있을 것 같습니다.