오늘은 Linked List 자료구조를 알아보자.
LinkedList는 뭘까?
LinkedList는 각 노드가 data과 pointer를 가지고 한 줄로 연결되어 있는 자료구조이다.
data를 가지고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다.
(LinkedList는 아래와 같이 단방향으로 표시할수도 있고, 양방향으로 표시할수도 있다.)
특징은 뭘까?
자료구조의 특징을 얘기할때 주로 삽입/삭제, 조회에 대해 얘기한다.
삽입/삭제
위의 그림에서 보면 LinkedList는 하나의 구조체 안에서 관리되는게 아니라 Node로 각자 관리되고 Node끼리 포인터로써 연결되어 있다.
ArrayList에서의 삽입/삭제
내부 배열에 객체를 저장해서 인덱스로 관리하는 ArrayList는 아래의 그림과 같은 삽입/삭제 과정을 거친다.
New라는 객체를 삽입하기 위해서는 New가 들어갈 index 이후의 객체들을 한 칸씩 미룬 후 New객체를 삽입한다.
2라는 객체를 삭제하기 위해서는 2라는 객체를 삭제하고 그 이후의 객체들을 한 칸씩 당겨줘야한다.
LinkedList에서의 삽입/삭제
pointer로 체인처럼 관리하는 LinkedList는 아래의 그림과 같은 삽입/삭제 과정을 거친다.
New라는 data를 가진 Node를 삽입하기 위해서는 0 Node의 Next를 New Node에 연결하고, New Node의 Next를 1 Node에 연결한다.
1 Node를 삭제하기 위해서는 0 Node의 Next를 수정하면 된다.
결론
삽입/삭제 측면에서 보면 LinkedList가 인덱스를 당기고 늘리는 추가 작업 없이 간단해 보인다.
(시간 복잡도에 대해 얘기할 수 있지만 조만간 기술면접 카테고리를 포스팅할 예정인데 거기서 다뤄보겠다.)
조회
ArrayList와 LinkedList의 조회는 각자가 갖는 특성에 의해 다르게 나타난다.
ArryaList는 index가 존재한다.
이 얘기는 즉 index를 통해 바로 접근이 가능하다는 얘기다.
LinkedList는 index가 존재하지 않는다.
위의 그림처럼 우리는 LinkedList의 시작 Node를 알고 있다.
그렇다면 우리가 원하는 Node를 찾기 위해서는 시작 Node에서 next pointer를 타고 순차적으로 검색해야한다.
그럼 언제 무엇을 사용하지?
우리는 LinkedList의 특징을 살펴보며 알게된 것들이 있다.
- LinkedList는 삽입/삭제시 앞뒤 링크만 변경되므로 삽입/삭제시 용이하다.
- LinkedList는 index가 없기 때문에 특정 요소에 접근하기 위해서는 순차적으로 탐색해야한다.
즉, 삽입/삭제가 많이 일어난다면 LinkedList가 유리하지만 조회가 많은 곳에서는 LinkedList가 불리하다.
LinkedList 종류
그림의 위쪽 LinkedList는 Single LinkedList(단일 링크드 리스트)이다.
그림의 아래쪽 LinkedList는 Double LinkedList(양방향 링크드 리스트)이다.
그림에서 알 수 있듯 Double LinkedList는 prev pointer Field가 추가되었다.
Double LinkedList는 Node가 양쪽으로 연결되어있다.
Single LinkedList는 요소를 탐색하기 위해서는 Next를 통해 한 방향으로만 가능하다.
하지만 Double LinkedList는 이전 Node와 다음 Node 양방향으로 탐색이 가능하다.
마무리
오늘은 LinkedList의 특징에 대해서 알아봤다.
다음 포스팅에서 JAVA와 Swift로 LinkedList를 구현해볼거다.
또한, 이후에 기술 면접 포스팅에서 Array, ArrayList, LinkedList에 대해서 비교 분석해볼 예정이다.
그럼 오늘도 이만!👋
