[DataStructure&Algorithm] LinkedList

자료구조 및 알고리즘

---

개요 - LinkedList란?

LinkedList란 말 그대로 Link되어 있는 List라는 뜻이다. LinkedList의 한 원소는 노드(node)라고도 하며, 하나의 노드에는 value와 pointer가 존재한다.

value에는 초기에 넣은 값이 존재하며, pointer는 다음 노드를 가리키게 된다. LinkedList는 선형과 원형 2가지의 형태가 존재하는데, 마지막 노드의 pointer값이 null인 경우는 선형 LinkedList, 마지막 노드의 pointer값이 맨 앞의 노드를 가리킨다면, 꼬리를 무는 형태가 되어 원형 LinkedList라고 한다.

 

자바에서는 CircularLinkedList는 구현되어 있지 않으므로, 궁금하다면 검색을 통해 공부하는 것이 좋을 것같다.

 

LinkedList에서 노드를 추가할 때는, 들어가고자 하는 자리 앞의 노드의 next potiner가 현재 삽입하려고하는 노드를 가리키게하고, 삽입하려고하는 노드의 next pointer가 다음 노드를 가리키게하면 자연스럽게 삽입 연산이 된다.

삭제를 할 때는, 삭제하고자하는 노드의 이전 노드에서 그 다음 노드를 가리키게되면 자연스럽게 삭제 연산이 된다.

 

따라서, 삭제와 수정, 추가가 용이하다는 것을 알 수 있다.

---

특징

• 각 노드는 다음 노드를 가리키고있다.
• 크기가 정해져있지 않아, 공간을 확보할 필요가 없다.
• 데이터의 추가 및 수정, 삭제가 용이하다.
• 연결구조를 위한 별도의 공간이 필요하다.
• 노드 삭제시, 연결 재구성이 필요하다 (pointer 주소 변경)

---

선언 및 초기화

import java.util.LinkedList;

class Main{
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
    }
}

---

메서드

import java.util.LinkedList;

class Main{
    public static void main(String[] args) {
        // LinkedList 기본 선언
        LinkedList<String> list = new LinkedList<>();
    
        // 메서드들
        // 1. add() : 리스트의 맨 뒤에 추가
        list.add("A");
        list.add("B");
        list.add("C");
        
        // 2. add(index, element) : 리스트의 index에 element 추가
        list.add(1, "D");
        
        // 3. addFirst() : 리스트의 맨 앞에 추가
        list.addFirst("E");
        
        // 4. addLast() : 리스트의 맨 뒤에 추가
        list.addLast("F");
        
        // 5. get(index) : index에 해당하는 element 반환
        System.out.println(list.get(0));
        
        // 6. getFirst() : 리스트의 맨 앞 element 반환
        System.out.println(list.getFirst());
        
        // 7. getLast() : 리스트의 맨 뒤 element 반환
        System.out.println(list.getLast());
        
        // 8. remove(index) : index에 해당하는 element 삭제
        list.remove(0);
        
        // 9. removeFirst() : 리스트의 맨 앞 element 삭제
        list.removeFirst();
        
        // 10. removeLast() : 리스트의 맨 뒤 element 삭제
        list.removeLast();
        
        // 11. size() : 리스트의 크기 반환
        System.out.println(list.size());
        
        // 12. clear() : 리스트의 모든 element 삭제
        list.clear();
        
        // 13. isEmpty() : 리스트가 비어있는지 확인
        System.out.println(list.isEmpty());
        
        // 14. indexOf() : element의 index 반환
        list.add("A");
        list.add("B");
        list.add("C");
        System.out.println(list.indexOf("B"));
        
        // 15. contains() : element가 리스트에 포함되어 있는지 확인
        System.out.println(list.contains("B"));
        
        // 16. set(index, element) : index에 해당하는 element를 변경
        list.set(1, "D");
        
        // 17. toArray() : 리스트를 배열로 변환
        Object[] array = list.toArray();
        
    }
}

---

응용

• 어떠한 순서를 가진 데이터들을 처리할 때
• 이전의 값이 현재의 값에 영향을 줄 때