연결 리스트는 가변 길이의 객체 배열과 유사한 동적 데이터 구조입니다. 이는 데이터 저장 용량 제한이 없고 빠른 탐색 속도를 제공하여 데이터 구조의 여러 문제를 해결합니다. 기존 배열은 고정된 크기로 인해 데이터 삽입, 삭제, 수정 시 번거롭다는 단점이 있습니다. 이러한 단점을 극복하기 위해 연결 리스트는 동적 배열 역할을 수행할 수 있습니다.
연결 리스트의 기본 구조
연결 리스트를 구현하기 위해서는 두 가지 주요 고려 사항이 있습니다:
- 모든 데이터 타입을 저장할 수 있도록
Object타입을 사용합니다. - 데이터의 순서를 유지하기 위해 각 데이터는
Node클래스로 래핑됩니다.Node클래스는 실제 데이터와 다음 노드에 대한 참조를 포함합니다.
class Node {
Object data; // 저장할 데이터
Node next; // 다음 노드를 가리키는 참조
public Node(Object data) {
this.data = data;
this.next = null; // 초기에는 다음 노드가 없음
}
}
단일 연결 리스트 구현
Link 클래스는 연결 리스트의 전체적인 관리 역할을 수행하며, Node 클래스는 개별 노드의 연결을 관리합니다. Node 클래스는 외부에서 직접 접근할 수 없도록 Link 클래스의 내부 클래스로 선언하는 것이 좋습니다.
기본 기능 구현
다음은 Link 클래스와 내부 Node 클래스를 사용하여 연결 리스트를 구현하는 기본적인 예시입니다.
interface DynamicList {
void add(Object data); // 데이터 추가
int size(); // 요소 개수 반환
boolean isEmpty(); // 리스트가 비어있는지 확인
boolean contains(Object data); // 특정 데이터 포함 여부 확인
Object get(int index); // 인덱스로 데이터 가져오기
void set(int index, Object obj); // 인덱스로 데이터 수정
void remove(Object data); // 데이터 삭제
void clear(); // 리스트 비우기
Object[] toArray(); // 배열로 변환
}
class LinkListImpl implements DynamicList {
private class Node {
Object data;
Node next;
Node(Object data) {
this.data = data;
}
// 현재 노드 뒤에 새 노드 추가 (재귀적)
void addNode(Node newNode) {
if (this.next == null) {
this.next = newNode;
} else {
this.next.addNode(newNode);
}
}
// 특정 인덱스의 노드 가져오기 (재귀적)
Object getNode(int index) {
if (LinkListImpl.this.currentIndex++ == index) {
return this.data;
} else {
if (this.next != null) {
return this.next.getNode(index);
} else {
return null; // 인덱스 범위를 벗어남
}
}
}
// 특정 인덱스의 노드 데이터 수정 (재귀적)
void setNode(int index, Object newData) {
if (LinkListImpl.this.currentIndex++ == index) {
this.data = newData;
} else {
if (this.next != null) {
this.next.setNode(index, newData);
}
}
}
// 특정 데이터를 가진 노드 삭제 (재귀적)
void removeNode(Node previous, Object dataToRemove) {
if (this.data.equals(dataToRemove)) {
previous.next = this.next; // 현재 노드를 건너뛰도록 이전 노드의 next 변경
} else {
if (this.next != null) {
this.next.removeNode(this, dataToRemove);
}
}
}
// 특정 데이터 포함 여부 확인 (재귀적)
boolean containsNode(Object dataToFind) {
if (this.data.equals(dataToFind)) {
return true;
} else {
if (this.next != null) {
return this.next.containsNode(dataToFind);
} else {
return false;
}
}
}
// 배열로 변환 시 데이터 복사 (재귀적)
void copyToArray(Object[] array) {
array[LinkListImpl.this.currentIndex++] = this.data;
if (this.next != null) {
this.next.copyToArray(array);
}
}
}
private Node head; // 리스트의 첫 번째 노드
private int elementCount = 0; // 저장된 요소의 개수
private int currentIndex = 0; // 인덱스 관련 연산(get, set, toArray)을 위한 임시 변수
private Object[] tempArray = null; // toArray() 메서드에서 사용할 임시 배열
@Override
public void add(Object data) {
if (data == null) return; // null 값은 추가하지 않음
Node newNode = new Node(data);
if (head == null) {
head = newNode; // 첫 노드인 경우 head로 설정
} else {
head.addNode(newNode); // 첫 노드부터 재귀적으로 마지막 노드까지 찾아 추가
}
elementCount++;
}
@Override
public int size() {
return elementCount;
}
@Override
public boolean isEmpty() {
return elementCount == 0;
// 또는 return head == null;
}
@Override
public boolean contains(Object data) {
if (head == null) return false;
return head.containsNode(data);
}
@Override
public Object get(int index) {
if (index < 0 || index >= elementCount) {
return null; // 유효하지 않은 인덱스
}
this.currentIndex = 0; // 인덱스 카운터 초기화
return head.getNode(index);
}
@Override
public void set(int index, Object newData) {
if (index < 0 || index >= elementCount || newData == null) return; // 유효하지 않은 인덱스 또는 null 데이터
this.currentIndex = 0; // 인덱스 카운터 초기화
head.setNode(index, newData);
}
@Override
public void remove(Object dataToRemove) {
if (head == null || dataToRemove == null) return;
if (head.data.equals(dataToRemove)) {
head = head.next; // 삭제할 데이터가 헤드인 경우
} else {
head.removeNode(head, dataToRemove); // 헤드가 아닌 경우, 재귀적으로 탐색하여 삭제
}
elementCount--;
}
@Override
public void clear() {
head = null;
elementCount = 0;
System.gc(); // 가비지 컬렉션 요청 (메모리 해제)
}
@Override
public Object[] toArray() {
if (head == null) {
return new Object[0]; // 빈 리스트는 빈 배열 반환
}
tempArray = new Object[elementCount];
this.currentIndex = 0; // 배열 인덱스 카운터 초기화
head.copyToArray(tempArray);
return tempArray;
}
// main 메서드는 예시 실행을 위해 포함
public static void main(String[] args) {
DynamicList myList = new LinkListImpl();
System.out.println("Is empty? " + myList.isEmpty()); // true
myList.add("Apple");
myList.add("Banana");
myList.add("Cherry");
System.out.println("Size: " + myList.size()); // 3
System.out.println("Contains 'Banana'? " + myList.contains("Banana")); // true
System.out.println("Element at index 1: " + myList.get(1)); // Banana
myList.set(0, "Apricot");
System.out.println("Element at index 0 after set: " + myList.get(0)); // Apricot
myList.remove("Banana");
System.out.println("Size after removing Banana: " + myList.size()); // 2
System.out.println("Contains 'Banana' after removal? " + myList.contains("Banana")); // false
Object[] array = myList.toArray();
System.out.print("Array representation: ");
for (Object item : array) {
System.out.print(item + " "); // Apricot Cherry
}
System.out.println();
myList.clear();
System.out.println("Size after clear: " + myList.size()); // 0
}
}
종합 실전: 펫샵
인터페이스는 추상화를 제공하며, 클래스는 이 인터페이스를 구현하여 구체적인 동작을 정의합니다. 펫샵 예제에서는 Pet 인터페이스와 DynamicList 인터페이스를 활용하여 다양한 종류의 애완동물을 저장하고 관리하는 시나리오를 구현합니다.
// 펫의 기본 정보를 위한 인터페이스
interface Pet {
String getName();
int getAge();
}
// 펫샵 클래스
class PetShop {
private DynamicList allPets = new LinkListImpl(); // 애완동물 저장을 위한 연결 리스트
// 애완동물 추가
public void addPet(Pet pet) {
if (pet != null) {
allPets.add(pet);
}
}
// 애완동물 삭제 (equals 메서드 구현 필요)
public void deletePet(Pet pet) {
allPets.remove(pet);
}
// 이름 키워드로 애완동물 검색
public DynamicList searchPets(String keyword) {
DynamicList results = new LinkListImpl();
Object[] pets = allPets.toArray();
for (Object petObj : pets) {
Pet currentPet = (Pet) petObj;
if (currentPet.getName().contains(keyword)) {
results.add(currentPet);
}
}
return results;
}
}
// 강아지 클래스 (Pet 인터페이스 구현)
class Dog implements Pet {
private String name;
private int age;
public Dog(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String getName() { return name; }
@Override
public int getAge() { return age; }
// 삭제 및 검색을 위해 equals 메서드 구현
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Dog otherDog = (Dog) obj;
return age == otherDog.age && name.equals(otherDog.name);
}
@Override
public String toString() {
return "Dog [Name=" + name + ", Age=" + age + "]";
}
}
// 고양이 클래스 (Pet 인터페이스 구현)
class Cat implements Pet {
private String name;
private int age;
public Cat(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String getName() { return name; }
@Override
public int getAge() { return age; }
// 삭제 및 검색을 위해 equals 메서드 구현
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Cat otherCat = (Cat) obj;
return age == otherCat.age && name.equals(otherCat.name);
}
@Override
public String toString() {
return "Cat [Name=" + name + ", Age=" + age + "]";
}
}
// 메인 실행 클래스
public class LinkedListBasics {
public static void main(String[] args) {
PetShop shop = new PetShop();
shop.addPet(new Dog("Buddy", 3));
shop.addPet(new Dog("Max", 5));
shop.addPet(new Cat("Whiskers", 2));
shop.addPet(new Cat("Mittens", 4));
System.out.println("--- Initial Pets ---");
Object[] initialPets = shop.allPets.toArray(); // 직접 접근은 좋지 않으나 예시를 위해 사용
for(Object pet : initialPets) {
System.out.println(pet);
}
System.out.println("\n--- Removing Max ---");
shop.deletePet(new Dog("Max", 5));
System.out.println("Size after removal: " + shop.allPets.size());
System.out.println("\n--- Searching for pets with 'at' in name ---");
DynamicList searchResults = shop.searchPets("at");
Object[] foundPets = searchResults.toArray();
for(Object pet : foundPets) {
System.out.println(pet); // Mittens
}
}
}
연결 리스트는 동적으로 크기가 조절되는 데이터 컬렉션을 구현하는 데 유용한 자료구조입니다. 위 코드 예시들은 기본적인 연결 리스트의 동작 원리와 이를 활용한 실제 애플리케이션의 기초를 보여줍니다.