해당 게시물은 기존에 만들어진 자료 구조인 LinkedList 내의 데이터가 어떻게 동작하는지를 이해하기 위해 작성되었습니다.
개인적인 바램으로 대규모 시스템에서의 데이터를 다룰 때의 인사이트를 얻을 수 있었으면 좋겠습니다..
LinkedList는 삽입/삭제에 용이하다고 알려져 있기 때문에 이의 원리를 이해하고자 삽입/삭제에 초점이 맞추어져 있는 점 양해부탁드립니다..!
ArrayList와 LinkedList
[Data Structure] ArrayList 데이터 동적 할당
해당 게시물은 기존에 만들어진 자료 구조인 ArrayList 내의 데이터가 어떻게 동작하는지를 이해하기 위해 작성되었습니다. 개인적인 바램으로 대규모 시스템에서의 데이터를 다룰 때의 인사이트
chris-ground.tistory.com
위 게시물에서 List는 컴퓨터 공학적인 개념으로, 비연속적인 메모리 공간을 할당받으며, 포인터(pointer)등을 활용해서 순서를 보장한다고 말씀드렸습니다. 그리고, ArrayList는 실제 컴퓨터 공학 개념과는 다르게 배열로 구현되어 있는 것도 이제 알겠습니다. 그렇다면, List의 특징을 온전히 지닌 자료구조가 있을까요?? 그건 바로 LinkedList입니다.
index를 활용하는 배열과 ArrayList와는 달리, LinkedList는 삽입/삭제에서 앞, 뒤 포인터만 수정하면 되기 때문에 성능 이점을 가집니다. 하지만, 특정 요소로의 직접 접근은 불가능해, 모든 데이터를 다 탐색하는 선형 검색(Linear Search)를 해야한다는 단점이 존재합니다. 따라서! LinkedList는 index로 자료 검색을 하는 서비스에는 적합하지 않는 것 같습니다..!
List 인터페이스
public interface List<E> extends Collection<E> {
...
boolean addAll(int index, Collection<? extends E> c);
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
}여기에서 혼동되면 안되는 점은 위처럼 List 인터페이스가 index를 제공한다고 해서, List 자체가 배열은 아니라는 점입니다. index는 단순히 요소의 순서를 나타내고, 해당 요소에 접근하려면 직접 접근이 아니라, 처음부터 끝까지 순회하게 할 수도 있습니다. 즉, 인덱스가 있는 것과 내부적으로 배열을 사용하는 것은 다른 개념입니다.
결국, List 인터페이스의 indexing 기능은 인터페이스를 구현하는 구체적인 클래스로 어떤 자료구조를 사용하느냐에 따라 다르게 작동하는 것입니다. List 인터페이스는 단지 특정 index에 있는 요소를 검색, 교체, 삭제할 수 있는 연산을 정의할 뿐입니다. 실제 구현은 List를 구현하는 클래스에 달려있습니다.
링크드 리스트 (LinkedList)
: LinkedList는 한 줄로 연결되어 있고 데이터와 포인터의 요소를 지닌 자료구조입니다. 가장 첫번째와 마지막 Node 를 가리키기 위해 first, last 변수를 사용핳고 있고, size를 통해 전체 데이터의 갯수를 지니고 있습니다. 이는 배열과 달리, 고정된 메모리 크기가 정해져 있지 않기 때문입니다.
LinkedList 내 데이터
- LinkedList에서는 비연속적인 공간에 순서를 보장하기 위해 포인터와 유사한 역할을 띈, Node 데이터를 다루고 있었습니다.
- prev는 이전 Node, next는 다음 Node를 가리킵니다.
- item은 실제로 저장하고 있는 데이터를 나타냅니다.
- 위와 같이, 이전과 다음 노드를 가리키는 두 개의 포인터가 존재하는 LinkedList를 양방향 링크드 리스트(doubly Linked list)라고 합니다.
참고) LinkedList의 종류에는 설명드린 양방향(doubly) 말고도 각 노드 별 포인터가 하나씩만 존재하는 단뱡향(singly), 마지막 노드가 처음 노드를 가리키는 양방향 원형(doubly circular)가 존재합니다. 이 외에도 Node의 생성과 소멸의 비효율을 없애고자, 배열로 구현한 링크드 리스트도 존재합니다. 이에 기회가 된다면 추가적으로 다뤄보도록 하겠습니다.
LinkedList 데이터 삽입 (1) - last
- LinkedList의 기본적인 add() 메서드 호출 시, 가장 마지막에 데이터가 삽입(linkLast)됩니다.
- 가장 마지막에 있는 노드를 prev로, 현재 삽입된 e를 데이터로, 가장 마지막이기 때문에 next는 null로 새로운 Node 객체를 생성합니다. 그 후, 해당 Node 객체를 마지막 노드로 지정해 LinkedList를 관리하고 있습니다.
- 만약, 마지막 Node 객체가 null이라면 데이터가 한 개밖에 없는 것을 의미하기 때문에 first 즉, 첫번째 Node도 만든 새롭게 Node객체로 할당하여 관리합니다.
- 또한, 만약 기존에 마지막 노드가 있었을 경우에는 위 과정에서 새롭게 추가된 데이터(newNode)가 마지막 노드로 갱신이 되기 때문에, 기존의 마지막 노드로 있었던 Node 객체의 next를 newNode를 가리키게끔 관리하고 있습니다. 이런 구조로 봤을 때, 데이터를 삽입 시,전체 데이터를 순회하지 않아도 되는 점에서 성능 이점을 가지고 있는 것 같습니다!
LinkedList 데이터 삽입 (2) - first
- LinkedList의 기본적인 addFirst() 메서드 호출 시에는 가장 처음에 데이터가 삽입(linkFirst)됩니다.
- linkLast와 다른점은, 가장 처음이기 때문에 prev는 null로, 가장 처음에 있었던 노드를 next로 지정해 새로운 Node 객체를 생성해 첫번째 Node로 관리합니다.
- 또한, 첫번째 노드에 이미 값이 있었다면 첫번째 노드의 next가 새로운 데이터를 가리키도록 합니다.
LinkedList 데이터 삭제
1. 매개변수가 없는 데이터 삭제
- 가장 첫번째 Node를 삭제하기 위해서 unlinkFirst() 메서드를 호출합니다.
- 여기에서 unlinkFirst 키워드를 확인할 수 있습니다.
- 그렇다면 다른 remove 메서드는 어떻게 구현되어 있을까요??
2. index를 통한 데이터 삭제 / Object 데이터 삭제
- 데이터를 삭제하기 위해 index나 Object를 매개변수로도 전달할 수 있습니다.
- 이 때에도 유사하게 unlink 라는 메서드를 호출하고 있는 것을 확인했습니다. 그럼 이 unlink는 어떻게 동작할까요??
unlink()
- unlink가 무슨 말인지 이해하지 못해서 그림을 그려봤습니다. 빨간색 글씨는 별도로 삭제된 Node가 next or prev로 가리키는 Node 뜻합니다.
- case 1) 같은 경우, 첫번째 노드를 삭제할 때의 경우입니다. 이때는 삭제된 Node의 next Node를 frist로 지정합니다. (unlinkFirst)
- case 2) 같은 경우, 마지막 노드를 삭제할 떄의 경우입니다. 이때는 삭제된 Node의 prev Node를 last로 지정합니다.
- case 3) 같은 경우, 중간 노드를 삭제할 때의 경우입니다. 이 때는 삭제된 Node의 prev Node를 삭제된 Node의 next.prev로 지정하고, 삭제된 Node의 next Node를 삭제된 Node의 prev.nest로 지정합니다.
- 아하, 이렇게 데이터를 unlink 즉, 앞 뒤 포인터를 수정시킴으로써 데이터를 관리할 수 있는 것을 알 수 있습니다.
느낀 점
이전의 ArrayList나 HashMap보다는 개념적인 측면과 일치하는 면이 많아 이해하기가 그나마(?) 나았던 것 같습니다. 데이터의 삽입/삭제 측면에서 Node 객체의 next, prev의 포인터 역할로써 성능상 이점을 이루어 낼 수 있음을 알 수 있었습니다.
어떤 걸 더 학습해야할까요.. 어떻게 성장해야 할까요... 많은 생각이 드는 날이었습니다.
'Data Structure' 카테고리의 다른 글
| [Data Structure] HashMap key, value 데이터 관리 (0) | 2023.09.15 |
|---|---|
| [Data Structure] ArrayList 데이터 동적 할당 (0) | 2023.09.14 |
