링크드 리스트(Linked List)
개요
링크드 리스트(Linked List)는 데이터를 순차적으로 저장하는 배열과 달리, 떨어진 메모리 공간에 존재하는 데이터를 화살표(포인터)로 연결해서 관리하는 데이터 구조이다. 이 구조는 데이터의 동적 추가, 삭제에 유리하지만, 특정 위치의 데이터 검색에는 비효율적일 수 있다.
링크드 리스트의 구성 요소
- 노드(Node): 데이터를 저장하는 기본 단위로, 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성된다.
- 포인터(Pointer): 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간.
- 헤드(Head): 링크드 리스트에서 가장 처음 위치하는 노드를 가리킨다. 리스트 전체를 참조하는데 사용된다.
- 테일(Tail): 링크드 리스트에서 가장 마지막 위치하는 노드를 가리킨다. 이 노드의 링크 필드는
null을 가리킨다.
링크드 리스트의 종류
- 단방향 링크드 리스트(Singly Linked List): 각 노드가 다음 노드만 가리키는 형태.
- 양방향 링크드 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 모두 가리키는 형태.
- 원형 링크드 리스트(Circular Linked List): 마지막 노드가 처음 노드를 가리키는 형태.
링크드 리스트 구현 (Java)
Node 클래스
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}- Node 클래스는 데이터 필드와 다음 노드를 가리키는 링크 필드를 가진다.
LinkedList 클래스
public class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void append(int data) {
if (head == null) {
head = new Node(data);
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data);
}
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}LinkedList 클래스는 head 노드를 가지고 있으며, 노드를 리스트 끝에 추가하는 append 메소드와 리스트의 모든 노드를 출력하는 printList 메소드를 포함한다.
테스트 코드
public class LinkedListTest {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.printList(); // 출력: 1 2 3
}
}연결 리스트 삽입, 삭제 구현 (Java)
LinkedList 클래스에 삽입, 삭제 메소드 추가
public class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void append(int data) {
if (head == null) {
head = new Node(data);
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data);
}
}
public void insert(int data, int position) {
Node newNode = new Node(data);
if (position == 0) {
newNode.next = head;
head = newNode;
} else {
Node current = head;
for (int i = 0; i < position - 1; i++) {
if (current != null) {
current = current.next;
} else {
throw new IndexOutOfBoundsException("Position out of range");
}
}
newNode.next = current.next;
current.next = newNode;
}
}
public void delete(int data) {
if (head != null && head.data == data) {
head = head.next;
} else {
Node current = head;
while (current != null && current.next != null && current.next.data != data) {
current = current.next;
}
if (current != null && current.next != null) {
current.next = current.next.next;
} else {
throw new IllegalArgumentException("Value not found in the list");
}
}
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}- insert 메소드는 특정 위치에 노드를 삽입하고, delete 메소드는 특정 데이터를 가진 노드를 삭제한다.
테스트 코드
public class LinkedListTest {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.printList(); // 출력: 1 2 3
linkedList.insert(4, 0);
linkedList.printList(); // 출력: 4 1 2 3
linkedList.insert(5, 2);
linkedList.printList(); // 출력: 4 1 5 2 3
linkedList.delete(1);
linkedList.printList(); // 출력: 4 5 2 3
linkedList.delete(4);
linkedList.printList(); // 출력: 5 2 3
}
}더블 링크드 리스트 (Java)
Node 클래스
public class Node {
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}- Node 클래스는 이전 노드와 다음 노드를 가리키는 포인터를 가진다.
DoubleLinkedList 클래스
public class DoubleLinkedList {
Node head;
Node tail;
public DoubleLinkedList() {
this.head = null;
this.tail = null;
}
public void append(int data) {
if (head == null) {
head = new Node(data);
tail = head;
} else {
Node newNode = new Node(data);
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
public void insert(int data, int position) {
Node newNode = new Node(data);
if (position == 0) {
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
if (tail == null) {
tail = newNode;
}
} else {
Node current = head;
for (int i = 0; i < position - 1; i++) {
if (current != null) {
current = current.next;
} else {
throw new IndexOutOfBoundsException("Position out of range");
}
}
newNode.next = current.next;
if (current.next != null) {
current.next.prev = newNode;
}
current.next = newNode;
newNode.prev = current;
if (newNode.next == null) {
tail = newNode;
}
}
}
public void delete(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
return;
}
current = current.next;
}
throw new IllegalArgumentException("Value not found in the list");
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}- DoubleLinkedList 클래스는 양방향 연결 리스트를 표현한다. append, insert, delete 메소드가 포함되어 있으며, 각 노드는 이전 노드와 다음 노드를 가리킨다.
테스트 코드
public class DoubleLinkedListTest {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.append(1);
doubleLinkedList.append(2);
doubleLinkedList.append(3);
doubleLinkedList.printList(); // 출력: 1 2 3
doubleLinkedList.insert(4, 0);
doubleLinkedList.printList(); // 출력: 4 1 2 3
doubleLinkedList.insert(5, 2);
doubleLinkedList.printList(); // 출력: 4 1 5 2 3
doubleLinkedList.delete(1);
doubleLinkedList.printList(); // 출력: 4 5 2 3
doubleLinkedList.delete(4);
doubleLinkedList.printList(); // 출력: 5 2 3
}
}So...
링크드 리스트는 데이터의 동적 추가와 삭제에 유리한 자료 구조이다. 그러나 특정 위치의 데이터를 검색하는 데는 비효율적일 수 있다. 링크드 리스트의 여러 형태(단방향, 양방향, 원형)는 다양한 요구 사항에 맞게 사용될 수 있다. 각 형태는 데이터의 삽입, 삭제, 검색에 대해 서로 다른 성능 특성을 가지며, 사용 목적에 맞는 형태를 선택하는 것이 중요하다.
개발이란 무엇인가..를 공부하는 거북이의 성장일기 🐢