링크드리스트(LinkedList)의 개념과 연산 (ft. 장단점까지)

링크드리스트(LinkedList)의 개념과 연산 (ft. 장단점까지)

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘은 지난 시간에서 배운 Arraylist에 이어 Linkedlist에 대한 포스팅을 이어가겠습니다.

 

혹시 아직 Arraylist에 대해서 잘 모르신다면

 

아래 링크를 통해 읽고 오시는 것을 추천드립니다!!

 

 

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

 

 

 

- 링크드리스트(LinkedList)란?

먼저 LinkedList는 Node라는 객체로 구성이 되어 있습니다. 

이 노드는 데이터를 저장할 수 있는 필드와 다음 노드를 가리킬 수 있는 next pointer를 가지고 있고,

이 노드들이 다 연결된 형태를 우리는 LinkedList라고 합니다.

여기서 가장 앞에 위치한 노드를 우리는 Head라 하고

 

가장 끝에 위차한 노드를 Tail이라고 부르게 됩니다.

Tail은 다음에 가리킬 노드가 없기 때문에 Tail의 next point는 Null을 가리키게 됩니다.

 

 

- 링크드리스트(LinkedList) 검색하기

LinkedList의 검색 동작에 대해서 알아보겠습니다.

LinkedList는 Arraylist와는 다르게 인덱스를 통한 random access가 불가능합니다.

 

자신을 가리키고 있는 next pointer만을 통해서 접근을 할 수 있기 때문에

n개의 노드를 가지고 있는 LinkedList의 검색의 시간복잡도는 O(N)입니다.

 

왜냐하면 우리가 찾아가고자 하는 위치를

 

Head부터 Tail까지 끝까지 순회를 하면서 데이터를 찾아가야 하기 때문이죠.

 

 

 

 

- 링크드리스트(LinkedList) 데이터 추가하기

만약 데이터를 추가하고 싶다면

 

기본값으로 마지막 테일 노드의 다음에 붙인다고 생각하시면 됩니다.

 

추가 작업도 Head에서부터 제일 끝에 있는 Tail까지 하나씩 다 찾아간 다음에

 

테일이 가리키고 있는 Null에 추가 노드데이터를 넣게 됩니다.

이것을 찾아가는 과정에서 O(N)의 시간 복잡도를 소요하게 됩니다.

 

 

 

- 링크드리스트(LinkedList) 데이터 삽입하기

만약 LinkedList에서 노드 데이터를 제일 끝이 아니라 중간에 삽입한다고 생각해보겠습니다.

중간에 삽입할 때는 Arraylist와는 다르게 한칸씩 미뤄줄 필요는 없습니다. 

그냥 간단하게 포인터만 바꿔주면 삽입이 됩니다.

그러나 삽입하기 위해 찾아가는 과정이 O(N)이기 때문에 시간 복잡도는 O(N)이 되겠습니다.

그렇게해서 넣고자 하는 데이터의 위치를 기준으로 해서 privious 노드의 포인터가 자신을 가리키게 하고

pricious node가 가리키던 next node를 내가 next node로 가리키게 하면 완성이 되겠죠.

그리고 삽입을 할 때 중간이 아니라 Head에 삽입 하는 경우가 LinkedList에 있을 수 있습니다.

만약에 Array에서 무조건 0번째에 데이터를 삽입한다고 하면

 

전체 데이터를 다 뒤로 한칸씩 미뤄야해서 무조건 n번의 수행이 발생할 수밖에 없어서 굉장히 비효율적이겠죠.

그런데 Linkedlist같은 경우 데이터를 가장 앞에 삽입한다면

 

Head의 포인터만 설정해주면 되기때문에 오히려 굉장히 간단하게 추가가 가능합니다.

 

 

 

- 링크드리스트(LinkedList) 데이터 삭제하기

마지막으로 데이터 삭제하기에 대해 알아보겠습니다.

우리가 LinkedList에서 중간에 삭제하고자 하는 노드가 있어요.

이 노드를 찾아가는 과정은 Arraylist와 마찬가지로 O(N)이겠죠. 여기까지는 arraylist와 시간복잡도가 같습니다.

그런데 그 이후 Arraylist는 삭제한 데이터 인덱스 이후의 값들을 한칸씩 당겨와야 하는 반면

 

Linkedlist는 간단하게 포인터만 바꿔주면 되는 차이점이 있습니다.

예를 들어서 삭제하고자 하는 노트를 기준으로

 

이 노드의 privios 노드가 자기를 가리키는 것이 아니라

 

자신이 가리키고 있던 next node를 가리키게 합니다.

그리고 자신의 next point는 아무것도 가리키지 않게 되는 거죠. 

 

그러면 Java에서는 이 아무것도 참조하지 않는 이 객체를 garabe collector가 수거해가면서 

 

자동으로 삭제가 이루어지게 됩니다.

그러면 다시 최종적으로 예쁘게 연결된 LinkedList가 완성이 되겠죠.

Next point를 제대로 설정을 안해주면 뒤가 뚝 끊겨버리기 때문에 

 

뒤가 다 사라져버리는 불상사가 발생할 수 있습니다.

그렇기 때문에 잊지말고 연결을 잘 해주는 것이 중요합니다.

 

 

링크드리스트 LinkedList

 

 

-링크드리스트(LinkedlList)의 장점과 단점

-장점

1. LinkedList의 장점은 배열의 복사나 재할당없이 데이터 추가가 가능하다는 점입니다.
우리가 array를 구현했을 때 배열이 꽉차있었으면 데이터를 늘려준다음에 

기존에 있던 데이터를 다시 추가해주는 작업을 했습니다.
이런 과정이 없어도 된다는 점입니다.

2. 그리고 array같은 경우는 배열이 한 번 늘어나면 그 후의 데이터를 다 지웠어요.
다 지워서 데이터가 조금밖에 안 남아있어도 그 뒤에 있는 공간을 모두다 여전히 잡고 있게 됩니다.
그러나 LinkedList는 자기가 쓰는 공간 만큼만 늘었다 줄었다 하는 장점이 있겠죠.

 

 

- 단점

1. 대신 명확한 단점이 하나 있죠.

random access가 안되기 때문에 어떤 작업을 하던 간에

데이터를 찾아가는 과정에서 O(N)의 시간을 소요한다.
그래서 데이터 접근에 대한 시간이 늘어난다는 것이 단점입니다.

 

 

 

오늘은 이렇게 링크드리스트(LinkedList)에 대한 포스팅을 진행해보았습니다.

 

여러분의 궁금증이 조금이나마 해결되었길 바랍니다 :)

 

로스윗의 코딩캠프는

 

미래의 개발자 여러분을 응원합니다.

 

모두 화이팅!!

 

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!