[ C.S 지식 정리 : 자료 구조 ] 자료구조 : LinkedList.

 

 

 

 

[ C.S 지식 정리 : 자료 구조 ] 자료구조 :  LinkedList.

 

---

 

 

∇ CS지식 정리 _ 자료구조 : LinkedList.

목  차

1. LinkedList 컬렉션
    1-1 종류
    1-2 LinkedList vs ArrayList 특징 비교.
    
2. LinkedList 사용법.
    2-1 객체 생성
    2-2 요소 추가/삽입
    2-3 요소 삭제
    2-4 요소 검색
    2-5 요소 얻기
    2-6 요소 변경
    2-7 배열 변환
    2-8 순회(이터레이터)
    2-9 스택 & 큐 지원
    2-10 동기화 처리

 

 

---

 

Ⅰ. LinkedList 컬렉션.

---

   ★ Java의  "Linked List"는 "ArrayList"와 같이,

        '인덱스'로 접근하여 조회*삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징입니다.

 

   ★ ArrayList는 내부적으로 배열을 이용하여, 메서드로 이리저리 조작이 가능하게 만든 컬렉션이라면,

       Linked-List는 "노드(객체)" 끼리의 '주소' 포인터를 서로 가리키며, 링크(참조) 함으로써 이어지는 구조입니다.

 

 

Linked-List

 

         √ 위 그림을 보면, 

             "LinkedList"는 각각의 노드마다 화살표로 연결되어서 '리스트 형태'로 나열되어 있는 것을 볼 수 있습니다.

                   { 여기서 "노드"는 하나의 "객체" 라고 보면 됩니다 }

 

                 ==>> 즉, 객체를 만들면 객체의 주소가 생기게 되는데

                            노드마다 각기 객체의 주소를 서로 참조함으로써"연결 형태"를 구성하는 것 입니다.

 

 

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};

 

 

---

 

 

 

Ⅰ- ⅰ . LinkedList 종류.

---

     

            ◆ 단반향 연결 리스트 [ Singly Linked List ]

 

         

       √  다음 노드를 가리키기 위한, 포인터필드 "next" 만을 가지고 있는 "Linked-List"를 'singly linked list"라고 합니다.

                =>> 하지만, 단일 연결 시트는 {현재 요소에서 이전 요소로} 접근해야 할 때 매우 부적합한 특징. !

 

                     ->> 이를 극복한 것이 doubly linked list 구조입니다.

 

 

            ◆ 양방향 연결 리스트 [ doubly Linked List ]

 

 

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    Node prev; // 이전 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};

 

       √  '이중 연결' 이라서 대단한 것이 아니고,  기존의 '단일 연결 노드 객체'에서

            '이전 노드 주소'를 담고 있는 필드 prev가 추가된 형태를 doubly linked list라고 부릅니다.

 

              => singly linked list는 이동 방향이 단방향이기 때문에, 이를 보완하여 역순으로도 검색이 가능하도록 한 것 !

 

       √  doubly linked list는 singly linked list보다 각 요소에 대한 접근과 이동이 쉽기 때문에 기본적으로 많이 사용 !

 

 

 

 

실제로 Java의 컬렉션 프레임워크에 구현된 LinkedList 클래스는 doubly linked list로 구현 !

 

            ◆ 양방향 원형 연결 리스트 [ doubly circular  Linked List ]

 

       √  doubly linked list 보다 접근성이 더 개선된 dobly circular linked list도 있습니다.

 

              -> 첫번째 노드와 마지막 노드를 각각 연결시켜서,  "마치 원형 리스트" 인 것처럼 만들었다고 보면 됩니다.

 

                      ->> 티비 채널을 순회하거나, 오디오 플레이어와 같이 데이터를 순차적 방식으로 처리하다가

                               마지막 요소를 만나면 다시 처음 요소로 되돌아가는 애플리케이션에서 사용된다고 보면 됩니다.

 

 

---

Ⅰ- ⅱ . LinkedList  vs  ArrayList 특징 비교.

---

 

 

---

 

 

Ⅱ. LinkedList  사용법.

---

 

 

    ∇ LinkedList 클래스 역시, List 인터페이스를 구현하므로 ArrayList 클래스와 사용할 수 있는 메소드는 거의 동일합니다.

 

             ++ LinkedList는 List 자료구조 외에도, Stack이나 Queue 자료 구조로서도 이용이 가능하기 때문에

                     이를 위한 메서드들도 구현되어 있어서 내부 메서드 갯수가 컬렉션 중 가장 多

 

 

---

 

Ⅱ- ⅰ . LinkedList  객체 생성.

---

 

  ◆ LinkedList를 사용하기 위해선 상단에 패키지를 명시하여, import 해줘야 합니다.

 

import java.util.LinkedList;

 

// 타입설정 int 타입만 적재 가능
LinkedList<Integer> list = new LinkedList<>();

// 생성시 초기값 설정
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));

 

    ※ LinkedList의 선언은 ArrayList와 동일하지만, ArrayList처럼 초기 값을 미리 지정하는 기능은 제공 X.

 

             - > 내부 데이터 집합 구조가 배열처럼 미리 공간을 할당하고 사용하는 방식이 아니라,

                          데이터가 추가될 때마다 노드(객체)들이 생성되어 동적으로 추가되는 방식.

 

 

---

Ⅱ- ⅱ . LinkedList  요소 추가/삽입.

---

ArrayList 와 달리 LinkedList에는 add 메서드 종류가 4가지 입니다. 기본 add() 메소드는 addLast()와 동일합니다.

 

 

 

     ∇ LinkedList의 가장 큰 특징은,  ArrayList와 다르게 중간에 데이터가 추가되거나 중간에 있는 데이터가 삭제되어도

              앞으로 땡기거나 뒤쪽으로 미는 동작이 없습니다.

 

                -> 추가되거나 삭제 될 노드 위치의 바로 앞-뒤쪽에 있는 노드의 참조를 변경하기만 하면 됩니다.

                -> 배열과 달리, 할당이 고정된 크기 개념이 아니기 때문에, 메모리가 충분히 있는 한 무한정으로 요소 저장 가능.

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// 가장 앞에 데이터 추가
list.addFirst("new");

 

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// 가장 뒤에 데이터 추가
list.addLast("new");

 

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// index 1에 중간 위치에 데이터 10 추가
list.add(1, "new");

 

 

 

addFirst()와 addLast() 는 요소를 첫번째, 마지막에 추가하는 것이기 때문에 O(1) 의 시간이 걸립니다.
그러나 중간 삽입일 경우 중간에 삽입할 위치까지의 탐색을 필요하기 때문에 O(N)의 시간이 걸립니다.

 

 

---

 

Ⅱ- ⅲ . LinkedList  요소 삭제.

---

remove 메서드 역시 add 메서드 처럼 removeFirst() 와 removeLast() 는 O(1),

그외에는 탐색 시간이 필요하기에 O(N)이 걸립니다.

 

만일 값을 전부 제거하려면 clear() 메소드를 사용하면 됩니다.

 

 

 

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// 첫 번째 값 제거
list.removeFirst();

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// 마지막 데이터 제거
list.removeLast();

 

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// index 1 중간 위치 제거
list.remove(1);

 

 

// 모든 값 제거
list.clear();

 

참고로 모든 값들을 제거 한다고 해서 단번에 노드들이 제거되는 것이 아닌,

참조 체인을 따라가면서 일일히 null로 설정해주기 때문에 O(N)의 시간이 걸립니다..

---

 

 

 

Ⅱ- ⅳ . LinkedList  요소 검색.

---

리스트에서 요소가 있는지 없는지 검색하는 방법은 요소 자체가 리스트에 있는지 검사하는 contains() 메서드와

인덱스 위치도 반환해주는 indexOf() 메서드가 존재합니다.

 

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C")));

// 해당 값을 가지고 있는 요소 위치를 반환 (앞에서 부터 검색) 
list1.indexOf("B"); // 1

// 해당 값을 가지고 있는 요소 위치를 반환 (뒤에서 부터 검색) 
list1.lastIndexOf("D"); // -1 : 찾고자 하는 값이 없으면

 

LinkedList list1 = new LinkedList();
list1.add("1");
list1.add("2");

// list1안에 "1" 값이 있는지 확인
list1.contains("1"); // true


LinkedList list2 = new LinkedList();
list2.add("1");
list2.add("2");
 
// list1에 list2의 모든 노드가 포함되어 있는지 확인
list1.containsAll(list2); // true

 

 

 

---

Ⅱ- ⅳ . LinkedList  요소 얻기.

---

개별 단일 요소를 얻고자 하면 get 메서드로 얻어올 수 있습니다. 

 

단, LinkedList는 ArrayList와 달리 만일 100번째 노드를 확인하기 위해서는

첫 번째 노드부터 100번째 노드까지 참조를 따라서 일일히 이동해야 하기 때문에 탐색 성능은 좋지 않은 편입니다.

 

 

list.get(0); // 0번째 index 요소의 값 출력

 

 

---

Ⅱ- ⅳ . LinkedList  요소 변경.

---

set 메서드의 주의점은 아무리 LinkedList라고 해도 기본적으로 리스트 이기 때문에,

리스트의 크기(size)를 넘기는 인덱스를 할당하게 된다면 배열과 같이 IndexOUtOfBoundsException 예외가 발생합니다.

 

LinkedList<String> list = new LinkedList<>();
list1.add("10");
list1.add("20");
list1.add("30");
 
list1.set(1, "A"); // index 1번의 데이터를 문자열 "A"로 변경한다.
System.out.println(list1); // // [10, A, 30]

 

 

---

 

Ⅱ- ⅴ . LinkedList 배열 변환.

---

LinkedList는 배열은 아니지만 리스트 컬렉션이기 때문에 연속된 값으로서 배열로 변환이 가능합니다..

 

 

 

LinkedList<Number> list1 = new LinkedList<>();
list1.add(1);
list1.add(2);
list1.add(3);
list1.add(4);
 
Number[] arr = (Number[]) list1.toArray();
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4]

 

LinkedList<Number> list1 = new LinkedList<>();
list1.add(1);
list1.add(2);

Object[] tmp = {0, 1, 2, 3, 4, 5}; // 통째로 추가할 배열

Number[] arr = (Number[]) list1.toArray(tmp);
System.out.println(Arrays.toString(arr)); // [1, 2, null, 3, 4, 5]

 

toArray(Obejct[] objArr)메서드의 결과값 배열 출력에서 null이 삽입되어 있는 이유는 자바 메서드 스펙입니다.

javadoc에 따르면 삽입된 리스트의 길이를 알리기 위해서 일부로 null을 넣는다고 합니다.

 

 

---

Ⅱ- ⅵ . LinkedList 순회(이터레이터)

---

 

보통 ArrayList의 요소들을 순회할 일이 있다면 다음과 같이 for문으로 처리하는 것이 일반적.

 

 

 

몇몇 컬렉션에서는 저장된 요소를 Iterator 인터페이스로 읽어오도록 하는 순회 패턴을 지향합니다.

 

Collection 인터페이스에서는 Iterator 인터페이스를 구현한 클래스의 인스턴스를 반환하는 iterator() 메소드를 정의하여 각 요소에 접근하도록 정의 하고 있습니다.

 

따라서 Collection 인터페이스를 상속받는 List나 Set 인터페이스에서도 iterator() 메소드를 사용할 수 있습니다. (Map은 X)

Iterator it = list.iterator();
 
while(it.hasNext()) {
	Object obj = it.next();
	System.out.println(obj);
}

 

 

---

Ⅱ- ⅶ . LinkedList  스택 & 큐 지원

---

LinkedList는 리스트 용도로서 뿐만 아니라, 구조 특성상 Stack이나 Queue 로서도 이용이 가능합니다

 

 

 

---

Ⅱ- ⅷ . LinkedList  동기화 처리.

---

멀티 쓰레드 환경에서 동시에 컬렉션에 접근해 문제가 발생하는 것을 방지하기 위해

동기화 처리된 리스트를 반환받아 사용합니다.

 

/* ArrayList 동기화 처리 */
List<String> l1 = Collections.synchronizedList(new ArrayList<>());

/* LinkedList 동기화 처리 */
List<String> l2 = Collections.synchronizedList(new LinkedList<>());