1. 개념
1.1. 정의
연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드의 위치를 나타내는 포인터를 가지며, 이를 통해 연결된 방식으로 데이터를 저장하는 자료구조이다.
1.1.1. 관련 용어
노드(Node)
- 데이터 덩어리. 데이터와 포인터로 구성
- ArrayList와의 가장 큰 차이점
포인터(Pointer)
- 다음(혹은 이전) 노드의 위치를 나타냄
헤드(Head)
- 링크드 리스트의 첫 번째 노드
테일(Tail)
- 링크드 리스트의 마지막 노드
- 링크드 리스트의 마지막 노드에는 null을 가리키는 포인터가 포함되어 이를 확인함으로써 해당 노드가 테일임을 알 수 있음
1.2. 특징
1.2.1. 포인터를 통해 연결
각 노드에 다음 노드의 주소를 가리키는 포인터를 갖고 있어 모든 요소가 연결된다.
배열처럼 요소를 추가, 탐색, 삭제할 수 있으나, 각 요소에 인덱스가 존재하지 않는다. 링크드 리스트는 비연속적인 메모리에도 저장할 수 있어 필요한 만큼 메모리 공간을 사용할 수 있다.
1.2.2. 삽입과 삭제의 상수 시간
리스트 중간에 요소를 삽입할 때 배열과 달리 다른 요소를 이동시킬 필요가 없으며, 포인터만 수정하면 된다. 따라서 삽입과 삭제 작업은 시간 복잡도가 O(1)이다.
1.2.3. 포인터로 인한 메모리 사용 증가
각 노드가 다음 노드를 가리키는 포인터를 가지므로 배열보다 더 많은 메모리를 사용한다. 예를 들어, 링크드 리스트의 각 노드에 정수 하나만 저장하더라도 동일한 데이터를 저장하는 배열의 두 배에 달하는 메모리를 사용할 수 있다.
1.2.4. 임의 접근 불가
컴퓨터 과학에서 임의 접근(Random Access)이란 상수 시간 내 무작위로 데이터에 접근하는 경우를 의미한다.
링크드 리스트는 임의의 요소에 접근하기 위해 반드시 헤드에서 시작해 각 포인터를 따라야 한다. 따라서 특정 요소에 접근할 때 선형 시간 복잡도 O(n)을 따르며, 탐색 역시 같은 이유로 O(n)이다.
1.3. 유형
링크드 리스트는 단일 링크드 리스트, 이중 링크드 리스트, 환형 링크드 리스트로 나눌 수 있다.
1.3.1. 단일 링크드 리스트(Singly Linked List)
각 노드가 다음 요소를 가리키는 포인터만 가지고 있어, 헤드에서 시작해 마지막까지 한 방향으로만 이동할 수 있는 구조이다.
단일 연결 리스트는 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우 이후 자료들을 유실하기 때문에 안정적이지 않다.
1.3.2. 이중 링크드 리스트(Doubly Linked List)
각 노드가 다음 요소와 이전 요소를 가리키는 두 개의 포인터를 가지고 있어, 양방향으로 이동할 수 있다.
이로 인해 단일 링크드 리스트보다 손상에 강하나, 메모리를 더 많이 사용하고 관리할 포인터가 많아진다.
1.3.3. 환형 링크드 리스트(Circular Linked List)
마지막 노드가 첫 번째 노드를 가리키는 포인터를 가지므로, 리스트의 끝에서 처음으로 순환할 수 있는 구조이다.
시작과 끝이 명확하지 않은 데이터를 반복적으로 처리하는 시스템에 유용하게 사용된다.
2. 구현
링크드 리스트는 단일 링크드 리스트보다는 통상 이중 링크드 리스트를 많이 사용하므로 이중 링크드 리스트를 구현해보고자 한다.
자바로 이중 링크드 리스트를 구현하는 방법은 전적으로 하단의 자료를 참고하였으며
🛠️ Doubly LinkedList 실전 구현 강의 (JAVA)
Doubly LinkedList 자료구조 노드(객체)를 연결하여 리스트 처럼 만든 컬렉션 (배열이 아님) 노드들을 연결하여 목록을 구성하기에 용량(capacity) 개념이 없다. (무한정 저장 가능) 데이터의 저장순서가
inpa.tistory.com
특히 리스트 수정 시 head, tail, 이전 노드의 next, 다음 노드의 prev 등을 적절히 설정하는 부분을 주의깊게 보길 권한다.
자세한 코드는 다음과 같다.
package dataStructure;
import java.util.NoSuchElementException;
import java.util.Objects;
public class MyDoublyLinkedList<E> {
private Node<E> head; // 노드의 첫 부분을 가리키는 레퍼런스(포인터)
private Node<E> tail; // 노드의 끝 부분을 가리키는 레퍼런스
private int size; // 요소의 갯수
public MyDoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// inner static class
private static class Node<E> {
private E item; // 노드에 담을 데이터
private Node<E> next; // 다음 노드 객체 가리키는 레퍼런스
private Node<E> prev; // 이전 노드 객체 가리키는 레퍼런스
Node(Node<E> prev, E item, Node<E> next) {
this.prev = prev;
this.item = item;
this.next = next;
}
}
// =================================== 탐색 ============================================
// add, remove 위해선 추가 / 삭제할 요소 탐색이 선행되어야 함
// 1. 만약 요소의 위치가 헤드에 가깝다면 순차 방향 탐색
// 2. 만약 요소의 위치가 테일(size)에 가깝다면 역 방향 탐색
public Node<E> search(int index) {
Node<E> n = null; // 반환할 노드
if (index < (this.size / 2)) { // head에 가까움 => 순차 탐색
n = this.head;
for (int i = 0; i < index; i++) { // 노드의 next 자체가 다음 노드를 가리키기 때문에 index 전까지만 탐색
n = n.next;
}
} else { // tail에 가까움 => 역순 탐색
n = this.tail;
for (int i = this.size - 1; i > index; i--) { // prev도 상기 이유와 마찬가지로 인덱스 후까지만 탐색
n = n.prev;
}
}
return n;
}
public E get(int index){
// 1. 인덱스 유효성 검사
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index = " + index + "Size = " + size);
}
// 2. 탐색한 값 반환
return search(index).item;
}
public void set(int index, E value){
// 1. 인덱스 유효성 검사
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index = " + index + "Size = " + size);
}
// 2. search 메소드 통해 교체할 노드 가져옴
Node<E> replaceNode = search(index);
// 3. 해당 노드의 값 변경
replaceNode.item = value;
}
// 순차 검색, 위치 반환
public int indexOf(Object value){
Node<E> node= this.head;
int index = 0;
while(node != null){
if(Objects.equals(value, node.item)){ // String.equals() 와 달리 null도 비교 가능
return index;
}
index++;
node = node.next;
}
return -1;
}
// 역순 탐색, 위치 반환
public int lastIndexOf(Object value){
Node<E> node= this.tail;
int index = size - 1;
while(node != null){
if(Objects.equals(value, node.item)){
return index;
}
index--;
node = node.prev;
}
return -1;
}
public boolean contains(Object value) {
return indexOf(value) != -1; // -1 이 아니라는 말은 요소가 리스트에 존재한다는 것이다.
}
//==================================== 추가 ====================================
public void addFirst(E value) {
// 1. head 백업
Node<E> first = head; // 최초 삽입 시 null
// 2. 노드 추가, 새 노드의 prev, next 설정(최초 삽입 시 null)
Node<E> newNode = new Node<>(null, value, first);
// 3. 리스트의 사이즈 증가
this.size++;
// 4. head 업데이트 (최초 삽입 시 tail도 업데이트)
head = newNode;
if (first == null) { // 최초 삽입 시 tail 업데이트
tail = newNode;
} else {// 5. 기존 첫 번째 노드의 prev 설정(최초 삽입 시 null)
first.prev = newNode; // 추가되기 이전 첫 번째 노드에서 prev를 새 노드를 참조하도록 업데이트
}
}
public void addLast(E value) {
// 1. tail 백업(최초 삽입 시 null)
Node<E> last = tail;
// 2. 노드 추가, 새 노드의 prev, next 설정(최초 삽입 시 null)
Node<E> newNode = new Node<>(last, value, null);
// 3. 리스트 사이즈 증가
this.size++;
// 4. tail 업데이트(최초 삽입 시 head도 업데이트)
tail = newNode;
if (last == null) {
head = newNode;
} else { // 5. 기존 마지막 노드의 next 설정(최초 삽입 시 null)
last.next = newNode;
}
}
public boolean add(E value) {
addLast(value);
return true;
}
// 중간 위치 삽입
public void add(int index, E value) {
// 1. 인덱스 범위 체크
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("Index = " + index + "Size = " + size);
}
// 2. 추가할 index == 0, addFirst
if(index == 0){
addFirst(value);
return;
}
// 3. 추가할 index == size, addLast
if(index == size){
addLast(value);
return;
}
// 4. 추가하려는 위치의 다음 노드 얻기
Node<E> nextNode = search(index).next;
// 5. 추가하려는 위치의 이전 노드 얻기
Node<E> prevNode = nextNode.prev;
// 6. 새 노드 생성
Node<E> newNode = new Node<>(prevNode, value, nextNode);
// 7. 리스트 크기 증가
size++;
// 8. 이전 노드의 next를 새 노드에 연결
prevNode.next = newNode;
// 9. 다음 노드의 prev를 새 노드에 연결
nextNode.prev = newNode;
}
//======================================= 삭제 ===============================
public E removeFirst(){
// 1. 빈 리스트일 시 에러
if(head == null){
throw new NoSuchElementException();
}
// 2. 삭제할 첫 번째 노드의 데이터 백업(반환용)
E value = head.item;
// 3. 두 번째 노드 임시 저장
Node<E> first = head.next;
// 4. 첫 번째 노드 전부 삭제
head.next = null;
head.item = null;
// 5. 리스트 크기 감소
size--;
// 6. head가 기존 두 번째 노드 가리키도록 업데이트
head = first;
if(first == null){
// 7. 만일 빈 리스트가 될 경우 tail은 null 처리
tail = null;
} else { // 8. 빈 리스트가 아닐 경우 기존 두 번째 노드의 prev을 null 업데이트(기존 첫 번째 노드 삭제 반영)
first.prev = null;
}
// 8. 백업했던 기존 첫 번째 노드의 요소 반환
return value;
}
public E remove(){
return removeFirst();
}
public E removeLast(){
// 1. 빈 리스트일 경우 에러 처리
if (tail == null){
throw new NoSuchElementException();
}
// 2. 삭제할 마지막 노드 백업
E value = tail.item;
// 3. 마지막 노드의 이전 노드를 임시 저장
Node<E> last = tail.prev;
// 4. 마지막 노드 삭제
tail.item = null;
tail.prev = null;
// 5. tail 업데이트(이전 노드를 가리키도록)
tail = last;
// 노드 삭제로 인해 빈 리스트가 될 경우 head도 null
if (last == null){
head = null;
} else {
// 아닐 경우 기존 마지막 노드의 이전 노드가 마지막 노드가 되기에 해당 노드의 next를 null 처리
last.next = null;
}
// 6. 반환
return value;
}
// 인덱스로 요소 삭제하기
public E remove(int index){
// 1. 인덱스 범위 유효성 체크
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index = " + index + "Size = " + size);
}
// 2. 첫 번째 인덱스이면 removeFirst, 마지막 인덱스일 시 removeLast
if (index == 0){
return removeFirst();
}
if (index == size - 1){
return removeLast();
}
// 3. 중간 인덱스일 경우
// 3.1. 삭제할 위치의 노드 탐색
Node<E> deleteNode = search(index);
// 3.2. 해당 노드의 데이터 백업
E value = deleteNode.item;
// 3.3. 해당 노드의 이전 노드 저장
Node<E> prevNode = deleteNode.prev;
// 3.4. 해당 노드의 다음 노드 저장
Node<E> nextNode = deleteNode.next;
// 3.5. 해당 노드 내부 요소 전부 삭제
deleteNode.item = null;
deleteNode.next = null;
deleteNode.prev = null;
// 4. 크기 감소
size--;
// 5. 이전 노드가 해당 인덱스 노드의 다음 노드 가리키도록 업데이트
prevNode.next = nextNode;
// 6. 다음 노드가 해당 인덱스 이전 노드 가리키도록 업데이트
nextNode.prev = prevNode;
// 7. 삭제한 노드의 데이터 반환
return value;
}
// 값으로 요소 삭제하기
// => search 메소드를 사용할 수 없어 직접 순회해야함
public boolean remove(Object value){
// 1. 삭제 노드 저장할 변수 선언
Node<E> delNode = null;
// 2. 리스트를 루프할 변수 선언
Node<E> i = head; // 첫 번째 노드부터 루프
// 3. 노드의 next를 순회하며 일치하는 값 탐색
while(i != null){ // 마지막 노드까지
if(Objects.equals(value, i.item)){
delNode = i;
break;
}
i = i.next; // 다음 노드로 이동
}
// 4. 찾는 요소가 없을 시 false 반환
if(delNode == null){
return false;
}
// 5. 삭제 작업 실시
// 5.1. (삭제 대상이)첫 번째 노드일 시
if(delNode.prev == null){
removeFirst();
return true;
}
// 5.2. 마지막 노드일 시
if(delNode.next == null){
removeLast();
return true;
}
// 5.3. 중간 노드일 시
// 5.3.1. 해당 노드 이전 노드와 다음 노드 저장
Node<E> prevNode = delNode.prev;
Node<E> nextNode = delNode.next;
// 5.3.2. 해당 노드 삭제
delNode.item = null;
delNode.prev = null;
delNode.next = null;
// 5.3.3. 리스트 크기 감소
size--;
// 5.3.4. 해당 노드의 이전 노드와 다음 노드를 서로 연결
prevNode.next = nextNode;
nextNode.prev = prevNode;
return true;
}
// 모든 요소 삭제
public void clear(){
Node<E> node = this.head;
while(node != null){
Node<E> next = node.next;
node.prev = null;
node.item = null;
node.next = null;
node = next;
}
head = null;
tail = null;
size = 0; // 크기 초기화
}
// ====================================================== 기타 함수 ==================================
public int size(){
return this.size;
}
public boolean isEmpty(){
return size == 0;
}
@Override
public String toString(){
if(head == null) {
return "[]";
}
StringBuilder result = new StringBuilder("[");
Node<E> n = head;
while(n == null) {
result.append(n.next.item);
if(n.next != null){
result.append(", ");
}
n = n.next;
}
result.append("]");
return result.toString();
}
}
3. 활용
링크드 리스트는 다양한 시스템에서 삽입과 삭제가 자주 발생하는 작업에 유용하게 사용된다. 구체적인 활용 사례는 다음과 같다.
3.1. 운영 체제의 메모리 관리 시스템
운영 체제는 주기적으로 메모리를 할당하고 해제하는 작업을 수행하며, 이 과정에서 메모리 단편화(Memory Fragmentation)1를 최소화하기 위해 링크드 리스트를 사용한다.
- 각 메모리 블록을 노드로 정의하고, 노드의 포인터를 통해 메모리 블록 간 연결을 관리
- 불연속적인 메모리 블록을 유연하게 연결할 수 있어, 메모리 활용도를 높이고 조각화를 줄이는 데 도움
3.2. 데이터베이스 관리
데이터베이스는 특정 데이터를 삽입, 삭제, 갱신하는 작업이 빈번히 발생하며, 링크드 리스트는 이를 처리하는 데 유리하다.
- 링크드 리스트를 사용하여 테이블의 레코드를 연결함으로써 삽입과 삭제 작업의 효율성 제고
- 인덱스 트리나 B-트리(B-Tree)2 같은 고급 자료구조에서도 노드 연결에 링크드 리스트 사용
3.3. 비즈니스 시스템
회계, 재무, 금융 거래 시스템 등에서는 많은 데이터의 실시간 처리와 변경이 요구되며, 링크드 리스트의 삽입과 삭제의 효율성이 중요하다.
- 거래 내역을 노드로 연결하여 최신 거래 데이터를 앞쪽에 추가하는 방식으로 활용 가능
- 거래 기록을 역순으로 추적할 수 있는 기능이 필요한 경우, 이중 링크드 리스트가 유용하게 사용
3.4. 스택과 큐 자료구조 구현
스택과 큐는 링크드 리스트를 통해 간단히 구현할 수 있는 기본 자료구조이다.
- 스택: 노드 추가와 삭제를 리스트의 한쪽 끝에서만 수행하므로, addFirst()와 removeFirst() 메서드를 활용해 LIFO(Last In, First Out) 방식을 구현 가능
- 큐: 노드 추가와 삭제를 각각 리스트의 양쪽 끝에서 수행하므로, addLast()와 removeFirst() 메서드를 사용해 FIFO(First In, First Out) 방식을 구현 가능
3.5. 블록체인
블록체인은 각 블록이 이전 블록에 대한 포인터를 가지고 있는 구조로, 링크드 리스트와 유사한 방식으로 데이터가 연결된다.
- 링크드 리스트와 마찬가지로 불연속적인 데이터의 연결과 추적이 용이
- 각 블록이 이전 블록을 가리키는 포인터를 가지고 있어, 데이터 무결성과 일관성을 보장하는데 링크드 리스트의 구조적 특성을 활용 가능
3.6 환형 버퍼 (Circular Buffer)
환형 링크드 리스트는 스트림 데이터를 다루는 애플리케이션에서 순환 버퍼로 유용하게 사용된다.
- 예를 들어, 실시간 스트리밍 데이터 또는 네트워크 패킷 처리에서 연속적인 데이터를 계속해서 처리해야 할 때, 데이터의 시작과 끝을 명확히 할 수 없는 경우 환형 링크드 리스트를 사용해 처리 가능
- 데이터가 버퍼의 끝에 도달하면, 자동으로 처음으로 돌아가 데이터를 순환하는 방식으로 처리 가능
4. 참고자료
그림 1 : <연결 리스트>, 나무위키
그림 2 3 4 5 : 코리 알트호프 , <나의 첫 알고리즘+자료구조 with 파이썬>, 한빛미디어 , 2023
[자료구조] 이중 연결 리스트(Doubly Linked List)
원형 연결 리스트(circular linked list)원형 연결 리스트는 마지막 노드의 링크가 첫번째 노드를 가리키는 리스트를 말한다. 그렇기 때문에 한 노드에서 다른 모든 노드로 접근이 가능하게 된다. 보
velog.io
🧱 자바 LinkedList 구조 & 사용법 - 정복하기
LinkedList 컬렉션 자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다. ArrayList는 내부적으로 배열을 이용하
inpa.tistory.com
'자료구조와 알고리즘 > 자료구조' 카테고리의 다른 글
| [자료구조] 트라이(Trie) (2) | 2024.11.20 |
|---|---|
| [자료구조] 해시 테이블(Hash Table) (0) | 2024.10.14 |
| [자료구조] 힙(Heap) (1) | 2024.10.07 |
| [자료구조] 트리(Tree) (1) | 2024.10.06 |
| [자료구조] 큐(Queue) (0) | 2024.10.04 |