LinkedList

LinkedList

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크가 있음
• 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함

장점

• 삽입 및 삭제 연산이 빠름 : 데이터 요소를 추가하거나 삭제할 때, 인접한 노드들의 참조만 수정하면 되므로 배열과 달리 데이터의 이동이 필요하지 않고 이로 인해 상대적으로 빠름
• 크기 가변성 : 미리 크기를 지정할 필요가 없으며, 요소를 추가하거나 제거할때마다 크기 조절이 가능

단점

• 임의 접근이 느림 : 배열과는 다르게 특정 인덱스의 요소에 접근할 때 처음부터 순차적으로 찾아야 함
• 메모리 사용량이 높음 : 각 노드마다 데이터 요소와 다음 노드를 가리키는 참조를 저장해야 하므로 메모리 사용량이 더 높을 수 있다
• 반복 작업에도 느림 : 모든 요소를 순회하거나 검색해야 하는 경우, 배열보다 느릴 수 있다
• 캐시 지역성 부족 : 배열은 요소가 메모리에 연속적으로 저장되기에 cpu캐시의 지역성을 잘 활용 가능하지만, LinkedList는 각 요소가 불연속적으로 저장되어 캐시 지역성이 떨어질 수 있다

사용되는 경우

• 데이터의 삽입 및 삭제가 빈번하게 발생하는 경우
• 크기가 동적으로 변해야 하는 경우
• 임의 접근이 많이 발생하지 않고, 순차적으로 데이터를 처리하는 경우

LinkedList의 종류

1. singly linked list

• 단방향이기에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다

2. Doubly linked list

• 단순한 linked list에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조 뿐 아니라 이전요소에 대한 참조가 가능

class Node{
	Node next; // 다음 요소의 주소를 저장
    Node previous; // 이전 요소의 주소를 저장
    Object obj;	// 데이터를 저장
}

3. Circular linked list

• doubly linked list의 첫번째 요소와 마지막 요소를 서로 연결시킨 것
  이렇게 하면, 마지막요소의 다음요소가 첫번째 요소가 되고, 첫번째 요소의 이전 요소가 마지막 요소가 된다

LinkedList의 메서드

• add(element): LinkedList에 요소를 추가합니다. 일반적으로 리스트의 끝에 요소가 추가됩니다.

	linkedList.add("Apple");

• add(index, element): 지정한 인덱스 위치에 요소를 삽입합니다.

	linkedList.add(1, "Grape");

• remove(element): 리스트에서 특정 요소를 제거합니다.

	String removeElement = "Cherry";
        if (linkedList.contains(removeElement)) {
            linkedList.remove(removeElement);
            System.out.println("'" + removeElement + "' removed from the LinkedList.");
        } else {
            System.out.println("'" + removeElement + "' not found in the LinkedList.");
        }

• remove(index): 지정한 인덱스 위치의 요소를 제거합니다.
• get(index): 지정한 인덱스 위치의 요소를 반환합니다.
• set(index, element): 지정한 인덱스 위치의 요소를 새로운 요소로 대체합니다.

	linkedList.set(2, "Orange");
        System.out.println("Updated LinkedList after changing element at index 2: " + linkedList);

• size(): LinkedList의 현재 크기를 반환합니다.

	int size = linkedList.size();
        System.out.println("Size of the LinkedList: " + size);

• isEmpty(): LinkedList가 비어있는지 여부를 확인합니다.

	boolean isEmpty = linkedList.isEmpty();
        System.out.println("Is the LinkedList empty? " + isEmpty);

• clear(): LinkedList의 모든 요소를 제거하여 비웁니다.

	linkedList.clear();
        System.out.println("Cleared LinkedList: " + linkedList);

• contains(element): 주어진 요소가 LinkedList에 포함되어 있는지 확인합니다.
• indexOf(element): 주어진 요소의 첫 번째 발견 위치(인덱스)를 반환합니다. 없으면 -1을 반환합니다.
• lastIndexOf(element): 주어진 요소의 마지막 발견 위치(인덱스)를 반환합니다.

	String searchElement = "Banana";
        if (linkedList.contains(searchElement)) {
            int firstIndex = linkedList.indexOf(searchElement);
            int lastIndex = linkedList.lastIndexOf(searchElement);
            System.out.println("First Index of '" + searchElement + "': " + firstIndex);
            System.out.println("Last Index of '" + searchElement + "': " + lastIndex);
        } else {
            System.out.println("'" + searchElement + "' not found in the LinkedList.");
        }

테스트 코드