[자료구조] LinkedList

---

👉LinkedList 란?

• LinkedList란 Collection 프레임워크의 일부이며 java.util 패키지에 소속되어 있습니다
• 이 클래스는 데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있습니다. 데이터는 포인터와 주소를 사용하여 연결합니다.
• 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나,
• 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다.

• ArrayList와 마찬가지로 사용법 위주로 공부해보겠습니다.

---

👉LinkedList 사용법

1. LinkedList 선언하기

LinkedList li = new LinkedList(); 
// 타입 설정x Object로 입력

LinkedList<LinkedListDemo> demo = new LinkedList<LinkedListDemo>(); 
// List타입을 LinkedListDemo

LinkedList<Integer> i = new LinkedList<Integer>();
// int 타입으로 선언

LinkedList<Integer> i2 = new LinkedList<>(); 
// 타입 선언 생략도 가능

LinkedList<Integer> i3 = new LinkedList<Integer>(Arrays.asList(1, 2, 3)); 
// 초기 값 세팅
		
LinkedList<String> s = new LinkedList<String>(); 
// String 타입 사용

LinkedList<Character> ch = new LinkedList<Character>(); // Char 타입 사용

• LinkedList 선언은 ArrayList선언 방식과 같지만
  LinkedList에서는 초기의 크기를 미리 생성할수는 없습니다.
• Class, Integer, String, Character 등의 타입으로 선언이 가능합니다

2. LinkedList 값 추가하기

import java.util.LinkedList;

public class LinkedListDemo {
	public static void main(String[] args)  {
		LinkedList<String> ll = new LinkedList<String>();
		
		ll.add("Hello");
		ll.add("Hello");
		ll.add(1, "World");
		
		System.out.print(ll);
	}
}

• LinkedList의 값을 추가하기 위해서 사용되는 add() 메서드는 2가지 사용법이 있습니다.
• add(Object) : 기본적으로 add를 사용하여 추가하면 LinkedList의 마지막에 데이터를 추가합니다
• add(int Index, Object) : LinkedList의 Index에 데이터를 추가합니다

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);//가장 앞에 데이터 추가
list.addLast(2);//가장 뒤에 데이터 추가
list.add(3);//데이터 추가
list.add(1, 10);//index 1에 데이터 10 추가

• addFirst(value) 함수를 사용하게 되면 가장 앞에 있는 Header의 값이 변경됩니다.
• addLast(value) 메소드를 사용하면 LinkedList 맨 뒤에 데이터가 추가됩니다.

3. LinkedList 값 삭제하기

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5));
list.removeFirst(); //가장 앞의 데이터 제거
list.removeLast(); //가장 뒤의 데이터 제거
list.remove(); //생략시 0번째 index제거
list.remove(1); //index 1 제거
list.clear(); //모든 값 제거

• LinkedList의 값 제거는 추가와 비슷합니다.

4. LinkedList 값 변경하기

mport java.util.LinkedList;

public class LinkedListDemo {
	public static void main(String[] args)  {
		LinkedList<String> ll = new LinkedList<String>();
		
		ll.add("Hello");
		ll.add("Hello");
		ll.add(1, "World");
		
		System.out.println(ll);
		
		ll.set(1, "Hello");

		System.out.println(ll);
	}
}

• 위 코드를 예시로 set() 메서드를 이용해 World 였던 1번 index를
  Hello로 변경하는것을 확인할 수 있습니다.

5. LinkedList 크기 구하기

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.size()); //list 크기 : 3

• LinkedList의 크기를 구하려면 LinkedList의 size() 메소드를 사용하면 됩니다.

6. LinkedList 값 출력

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListDemo {
	public static void main(String[] args)  {
		LinkedList<String> ll = new LinkedList<String>();
		
		/* 값을 추가한다 */
		ll.add("Hello");
		ll.add("World");
		ll.add("Hello");
		ll.add("World");
		
		// get(i) 메서드를 사용하여 값 출력 
		for(int i = 0; i < ll.size(); i++)
			System.out.print(ll.get(i) + " ");
		
		System.out.println();

		// for문을 사용하여 값 출력 
		for(String str : ll)
			System.out.print(str + " ");
		
		System.out.println();

		// Iterator를 사용하여 값 출력 
		Iterator iter = ll.iterator();
		while(iter.hasNext())
			System.out.print(iter.next() + " ");
	}
}

• LinkedList의 값을 출력하는 메서드는 get(int Index) 가 있습니다.

7. LinkedList 값 찾기

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));

System.out.println(list.contains(1)); 
//list에 1이 있는지 검색 : true

System.out.println(list.indexOf(1)); 
//1이 있는 index반환 없으면 -1

• contains(Object) : LinkedList에서 값이 있는지 없는지 여부를 판단해 값이 있다면 true, 없다면 false를 반환 합니다.

• indexOf(Object) : LinkedList에서 값이 없다면 -1을 반환하고,
  값이 있다면 index 값을 리턴해줍니다.

---

퀴즈 : LinkedList는 노드간의 연결로 되어있고 각 노드에는 다음 노드를 지칭하는 정보가 담겨져있는 형태이다.
그렇다면 LinkedList의 중간 값을 삭제할 때 삭제된 노드는 여전히 다음 노드를 가리키고 있는데 이것은 어떻게 처리될까.

Array와 LinkedList의 삽입 삭제 접근의 동작을 시간복잡도와 연관지어 비교해 보자.

---

참고 자료
https://crazykim2.tistory.com/566
https://coding-factory.tistory.com/552