LinkedList(Single Linked List와 Double Linked List)란? / LinkedList 메서드 정리

LinkedList는 자료구조 중 하나로, 데이의 선형 리스트를 노드라는 개별적인 단위로 나타낸 것이다. 각 노드는 데이터와 그다음 노드에 대한 참조를 가지고 있다. 이렇게 서로 연결된 노드들의 체인을 통해 전체 데이터의 리스트를 표현한다.

 

 

 

 

연결리스트(Linked List)

하나의 개체를 이루는 노드가 연결되어 리스트를 이루는 구조이다.

 

노드에는 값을 담고 있는 데이터와 다음 노드를 가리키는 링크 정보를 저장하고 있다. 

데이터에는 숫자, 문자열, 또다른 연결 리스트 등 다양한 형식을 가질 수 있다. 

 

일반적으로 리스트의 맨 앞 노드를 헤드, 맨 마지막 노드를 테일이라고 한다.

 

이런 식으로 왼쪽엔 데이터 오른쪽엔 next링크 정보를 저장하고 있다.

 

배열과 연결리스트는 비슷해보이지만 다른 차이점을 가지고 있다. 

 

배열(Array):

• 인덱싱 : 배열의 주요 장점중 하나는 O(1)의 시간 복잡도로 임의의 인덱스에 위치한 데이터에 접근할 수 있다 
• 크기 변경의 어려움 : 배열은 고정 크기를 가짐
• 삽입과 삭제의 비효율성 : 모든 요소들을 이동시켜야 되므로 O(n)의 시간 복잡도를 가진다

연결 리스트 (Linked List):

• 임의의 접근의 어려움 : 연결 리스트에서는 각 요소가 메모리의 임의의 위치에 지정되고 각 노드는 다음 노드의 위치를 가리킨다. 이로 인해서 연결 리스트는 O(n)의 시간복잡도로 임의의 위치에 접근해야 한다.
• 동적 크기 : 연결 리스트는 노드를 추가하거나 삭제함으로써 동적으로 크기를 변경할 수 있다. 
• 삽입과 삭제의 효율성 : 연결 리스트에서는 노드를 추가하거나 삭제하는 게 매우 효율적이다. 새 노드를 추가하거나 기존 노드를 삭제하는 데는 몇 개의 참조를 변경하면 되므로 O(1)의 시간복잡도를 가진다. (단 삭제의 경우 삭제할 노드를 먼저 찾아야 돼서 O(n)의 시간복잡도가 소요될 수 있다.)

 

ArrayList와 Linkedlist도 각자 차이점이 있다. 

 

내부 구조:

• ArrayList는 내부적으로 배열을 사용하여 데이터를 저장한다. 이로인해 인덱스를 기반으로 데이터에 빠르게 접근할 수 있다 하지만 크기 조정에는 상대적으로 느리다
• LinkedList는 노드(Node)의 이중 연결 리스트로 데이터를 저장한다. 각 노드는 데이터와 함께 다음 노드의 이전 참조를 가지고 있다. 이로 인해서 데이터의 삽입과 삭제가 빠르지만 특정 인덱스에 위치한 데이터에 접근할 때는 순차적으로 탐색해야 돼서 느리다

 

성능:

• ArrayList는 get()과 set()메서드를 통해 임의 접근에 강점을 가진다 반면에 add()와 remove() 메서드를 통한 삽입과 삭제는 비효율적이다. 
• LinkedList는 add()와 remove()메서드를 통해 리스트의 앞뒤에서의 삽입과 삭제에 강점을 가진다. 하지만 get()과 set() 메서드를 통한 임의의 접근은 비효율적이다.

 

용도:

• 인덱스를 통해 빠르게 접근해야 할 때 : ArrayList
• 데이터의 삽입과 삭제가 빈번하게 일어나는 경우 : LinkedList

 

---

단일 연결 리스트(Single Linked List)

단일 연결 리스트는 각 노드가 데이터와 다음 노드에 대한 링크를 가지고 있는 선형 리스트이다. 마지막 노드는 null을 가리키는 특징이 있다.

 

 

class Node {
    int data;
    Node next;  // 다음 노드를 가리키는 참조 변수

    // 노드 클래스의 생성자
    Node(int data) {
        this.data = data;  // 생성자를 통해 전달된 데이터를 저장
        this.next = null;   // 생성시에는 다음 노드가 없으므로 null로 설정
    }
}

public class SingleLinkedList {  
    Node head;   // 리스트의 첫 번째 노드를 가리키는 머리 노드 참조 변수
    
    public void add(int data) {  // 새로운 노드를 리스트의 끝에 추가하는 메소드
        
        Node newNode = new Node(data); // 새로운 노드 생성

        if(head == null) {  // 만약 리스트가 비어있다면 (즉, head가 null이라면),
            // head를 새 노드로 설정
            head = newNode;
        } else {
            // 리스트가 비어있지 않다면,
            // 리스트의 마지막 노드를 찾아서
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            // 찾은 마지막 노드의 next를 새 노드로 설정
            last.next = newNode;
        }
    }
}

이렇게 새 노드가 추가될 때마다 마지막 노드를 찾아 그 다음에 새 노드를 연결하는 방식으로 작동한다. 

 

 

---

 

 

이중 연결 리스트(Double Linked List)

이중 연결 리스트는 각 노드가 데이터의 뒤, 앞의 노드에 대한 링크를 가지고 있는 리스트이다. 이런 특징으로 양방향으로 리스트를 탐색하는 게 가능하다

 

 

class Node {
    int data; // 노드가 가지는 데이터
    Node previous;  // 이전 노드를 가리키는 참조 변수
    Node next;   // 다음 노드를 가리키는 참조 변수

    Node(int data) {  // 노드 클래스의 생성자
        this.data = data;  // 생성자를 통해 전달된 데이터를 저장
    }
}


public class DoubleLinkedList {

    Node head;  // 리스트의 첫 번째 노드를 가리키는 머리 노드 참조 변수
    Node tail = null;  // 리스트의 마지막 노드를 가리키는 꼬리 노드 참조 변수
    
    public void addNode(int data) {  // 새로운 노드를 리스트의 끝에 추가하는 메소드
    
        Node newNode = new Node(data);  // 새로운 노드 생성

        if(head == null) {   // 만약 리스트가 비어있다면 (즉, head가 null이라면),
        
            head = tail = newNode;  // head와 tail을 새 노드로 설정
            head.previous = null;  // 이 때, 첫 노드의 이전 노드는 없으므로 null로 설정
            tail.next = null;  // 첫 노드의 다음 노드도 없으므로 null로 설정
            
        } else { // 리스트가 비어있지 않다면,
            
            tail.next = newNode;  // 현재의 마지막 노드(tail)의 다음 노드를 새 노드로 설정
            newNode.previous = tail; // 새 노드의 이전 노드를 현재의 마지막 노드로 설정
            tail = newNode;   // tail을 새 노드로 업데이트
            tail.next = null;  // 새로운 마지막 노드의 다음 노드는 없으므로 null로 설정
        }
    }
}

 

 

---

메서드 정리

public static void main(String[] args) {

        // LinkedList 객체를 생성합니다.
        LinkedList<String> linkedList = new LinkedList<>();

        // add(E e) 메서드를 사용하여 요소를 추가합니다.
        linkedList.add("A");

        // add(int index, E element) 메서드를 사용하여 특정 위치에 요소를 추가합니다.
        linkedList.add(1, "D");

        // contains(Object o) 메서드를 사용하여 요소가 리스트에 포함되어 있는지 확인합니다.
        boolean contains = linkedList.contains("B");

        // get(int index) 메서드를 사용하여 특정 위치의 요소를 얻습니다.
        String element = linkedList.get(2);

        // remove(int index) 메서드를 사용하여 특정 위치의 요소를 제거합니다.
        String removedElement = linkedList.remove(0);

        // size() 메서드를 사용하여 리스트의 크기를 얻습니다.
        int size = linkedList.size();

        // set(int index, E element) 메서드를 사용하여 특정 위치의 요소를 다른 요소로 대체합니다.
        linkedList.set(0, "B");
        
        // clear() 메서드를 사용하여 리스트의 모든 요소를 제거합니다.
        linkedList.clear();
        
        // isEmpty() 메서드를 사용하여 리스트가 비어있는지 확인합니다.
        boolean empty = linkedList.isEmpty();
        
        // indexOf(Object o) 메서드를 사용하여 특정 요소의 인덱스를 얻습니다.
        int index = linkedList.indexOf("C");
        
        // addFirst(E e) 메서드를 사용하여 리스트의 맨 앞에 요소를 추가합니다.
        linkedList.addFirst("A");
        
        // addLast(E e) 메서드를 사용하여 리스트의 맨 뒤에 요소를 추가합니다.
        linkedList.addLast("D");
        
        // getFirst() 메서드를 사용하여 리스트의 맨 앞의 요소를 얻습니다.
        String firstElement = linkedList.getFirst();
        
        // getLast() 메서드를 사용하여 리스트의 맨 뒤의 요소를 얻습니다.
        String lastElement = linkedList.getLast();
        
        // removeFirst() 메서드를 사용하여 리스트의 맨 앞의 요소를 제거합니다.
        String removedFirstElement = linkedList.removeFirst();
        
        // removeLast() 메서드를 사용하여 리스트의 맨 뒤의 요소를 제거합니다.
        String removedLastElement = linkedList.removeLast();
        
    }