연결 리스트 (Linked List)

연결 리스트(Linked LIst)란?

각 데이터가 "다음 데이터가 어디 있는지"를 가리키는 화살표(참조)를 들고 있고, 그 화살표를 따라가면 줄줄이 이어지는 자료구조"

 

 

각 상자를 "노드(Node)"라고 부르고, 노드는 두 부분으로 이루어진다.

- 데이터(data) : 실제 값

- 다음 노드를 가리키는 참조(next) : 다음 노드의 주소

- 마지막 노드의 next는 null -> "더 이상 다음이 없다"는 뜻

 

1. 노드 클래스 만들기

class Node {
	int data; // 데이터
    Node next; // 다음 노드를 가리키는 참조
    
    Node(int data) {
    	this.data = data;
        this.next = null; // 처음엔 다음이 없음
    }
}

 

2. 노드들을 직접 연결해보기

public class LinkedListBasics {
	public static void main(String[] args) {
    	
        // 노드 3개 생성
        Node first = new Node(10);
        Node second = new Node(20);
        Node third = new Node(30);
        
        // 화살표 연결 : first -> second -> third
        first.next = second;
        second.next = thrid;
        
        // head는 first를 가리킴
        Node head = first;
        
        // head부터 화살표를 따라가며 순회
        Node current = head;
        
        while (current != null) {
        	System.out.print(current.data + " -> ");
            current = current.next; // 다음 노드로 이동
        }
    
    	System.out.println("null");
    }
}

 

3. 실무에서 주로 사용하는 LinkedList 클래스 생성

class Node<T> {
	T data; // 데이터
    Node<T> next; // 다음 노드를 가리키는 참조
    
    Node(T data) {
    	this.data = data;
        this.next = null; // 처음엔 다음이 없음
    }
}

class MyLinkedList<T> {
	private Node<T> head;
    
    // 맨 끝에 노드 추가 - O(n), head부터 끝까지 따라가야 함
    public void addLast(T data) {
    	Node<T> newNode = new Node<>(data);
        
        if (head == null) {
        	head = newNode;
            return;
		}
        
        Node<T> current = head;
        while (current.next != null) {
        	current = current.next;
		}
    	
        current.next = newNode; // 마지막 노드의 next를 새 노드로 연결
    }
    
    // 맨 앞에 노드 추가 - O(1), 화살표 한 번만 바꾸면 끝
    public void addFirst(T data) {
    	Node<T> newNode = new Node<>(data);
        newNode.next = head; // 새 노드가 기존 head를 가르키게
        head = newNode; // head를 새 노드로 교체
    }
    
    // 특정 값을 가진 첫 노드 삭제 - O(n)
    public void remove(T value) {
    	if (head == null) return;
        
        if (head.data.equals(value)) {
        	head = head.next; // head를 건너뛰고 다음 노드로 교체
            return;
		}
        
        Node<T> current = head;
    	while (current.next != null) {
        	if (current.next.data.equals(value)) {
            	current.next = current.next.next; // 화살표를 건너뛰어 연결
                return;
            }
            
            current = current.next;
    	}
        
    }
    
    // 전체 출력
    public void printList() {
    	Node<T> current = head;
        while (current != null) {
        	System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
    
}

class Student {
	String name;
    int score;
    
    Student(String name, int score) {
    	this.name = name;
        this.score = score;
    }
    
    @Override
    public String toString() {
    	return name + "(" + score + "점)";
    }
}

public class LinkedListEx {
	public static void main(String[] args) {
    	MyLinkedList<Student> studentList = new MyLinkedList<>();
        
        studentList.addLast(new Student("철수", 90));
        studentList.addLast(new Student("영희", 85));
        studentList.addFirst(new Student("민수", 100));

        studentList.printList();
        // 출력: 민수(100점) -> 철수(90점) -> 영희(85점) -> null

        // 문자열만 담는 리스트도 같은 클래스로 만들 수 있음
        MyLinkedList<String> nameList = new MyLinkedList<>();
        nameList.addLast("Alice");
        nameList.addLast("Bob");
        nameList.printList();
        // 출력: Alice -> Bob -> null
    }
}