[Swift CS Study] Linked List

21.06.13

공부한 것을 정리하는 용도의 글이므로 100% 정확하지 않을 수 있습니다.
참고용으로만 봐주시고, 내용이 부족하다고 느끼신다면 다른 글도 보시는 것이 좋습니다.
+ 틀린 부분, 수정해야 할 부분은 언제든지 피드백 주세요. 😊

                                                 by. ryalya

🔶 Linked List란?

🔹 자료구조란?

먼저 List는 자료구조(Data structure)중 하나로 Java Collection framework에서 지원한다. (Java, C, C++에서 지원)

자료구조는 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Nonlinear Data Structure)로 나눌 수 있다.

선형 자료 구조

• 데이터가 일렬로 연결된 형태 ex)double[], int[]
• 선형 자료구조는 대표적으로 리스트(List)와 큐(Queue), 덱(Deque)이 있음.
  
  

비선형 자료 구조

• 각 요소가 여러 요소와 연결된 형태.
• 비선형 자료구조는 대표적으로 그래프(Graph)와 트리(Tree)가 있음.
  
  

🔹 자료 구조 계층

• 점선은 구현 관계이고, 실선은 확장 관계. (인터페이스끼리는 다중 상속 가능)
• 자료구조들은 각각 '구현'이 되어 class로 제공됨. 녹색 부분이 '구현된 자료구조'
• Iterable이 Collection보다 위에 있는 이유는??
  제공하고 있는 class 들은 모두 객체형태로 내부 구현 또한 대개 Object[] 배열 형태가 아니라 각각의 객체를 갖고 움직임. 그래서 객체의 데이터들을 모두 순회하면서 출력하려면 사용자들이 각각의 데이터 순회 방법을 알거나 하나씩 get() 같은 메소드를 통해 데이터를 하나씩 꺼내와야 한다.
  
  

🔹 Linked List

Linked List는 Array List와 함께 Java에서 제공하는 List 인터페이스를 구현한 Collection을 말한다.

LinkedList는 데이터(item)와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식을 말한다.

데이터와 주소로 이루어진 클래스를 Node(노드)라고 한다.
각각의 노드는 데이터와 함께 이전의 노드와 다음 노드를 연결하는 방식으로 이전 노드와 다음 노드의 값을 가지고 있다.(이중 연결 리스트, 양방향 리스트 라고도 함.)

즉, LinkedList는 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다고 볼 수 있다.

LinkedList는 데이터를 추가하거나 삭제하는 것이 원활하다. 어느 위치에서든 추가나 삭제를 할 경우 변경되는 노드만 다시 연결해주면 되기 때문이다.

하지만 데이터가 연결되어 있다보니 요소를 검색해야 할 경우 처음 노드부터 찾으려는 노드가 나올 때 까지 연결된 노드들을 모두 방문해야한다는 점에서는 효율이 떨어진다.

그래서 주로 ArrayList는 검색이 많은 경우에 사용하고 LinkedList는 잦은 삽입/삭제 시 사용한다.

🔶 Linked List 사용법

Linked List 선언 및 사용 방법은 Array List와 같다.

1. Linked List 선언

먼저 linked list를 생성하기 위해서는 linked list 패키지를 import해줘야 한다.

import java.util.LinkedList;

아래 예시는 linked List를 선언(생성)하는 방법이다.

<예시>
# 1.
LinkedList<Integer> int1 = new LinkedList<Integer>(); // 타입 지정
LinkedList<String> str1 = new LinkedList<String>();
# 2.
LinkedList<Integer> int2 = new LinkedList<>(); // 타입 생략 가능
# 3.
LinkedList none = new LinkedList(); // 타입 미설정 → Object로 선언됨.
#4.
LinkedList<Integer> int3 = new LinkedList<Integer>(Arrays.asList(1,2)); // 생성시 값 가가
#5.
LinkedList<Person> people = new LinkedList<Person>(); // 타입설정 Person객체만 사용가능

예시 1과 같이 타입을 지정해줄 수도 있고, 타입을 생략해서 생성할 수도 있다.
또한 값이 있는 형태, 객체를 지정해준 형태로 생성할 수도 있다.

2. 값 추가

먼저 Int형 Linked list를 선언해준다.

<예시>
LinkedList<Integer> list = new LinkedList<Integer>();

<예시>
# 1. 
list.add(3);
# 2.
list.addFirst(1);
# 3.
list.addLast(2);

Linked List는 add를 사용하여 값을 추가할 수 있다. add(value)로 사용할 경우, 값(데이터)은 가장 마지막에 추가된다.

.addFirst()를 사용하면 가장 앞에 데이터를 추가하고,
.addLast()를 사용하면 마지막(가장 뒤)에 데이터를 추가할 수 있다.

특정 위치에 값을 추가할 수도 있는데

list.add(1, 10);

add(index,value)에서 콤마(1,10)를 기준으로 앞은 index '1'뒤에 데이터 '10'을 추가하라는 것이다.

3. 값 변경

<예시>
LinkedList<String> animals = new LinkedList<>();
// add() method
animals.add("cat");
animals.add("dog");
animals.add(0, "sheep");
animals.add("pig");

// set() method
animals.set(0, "fox");

System.out.println(animals);

Linked List는 set()을 이용하여 특정 위치의 값을 변경할 수 있다.
set(index, value)로 index위치에 value값을 넣으라는 뜻!

set()을 실행하기 전까지 animals를 출력하면 sheep, cat, dog, pig가 나왔겠지만
set()을 실행한 후 animals를 출력하면 fox, cat, dog, pig가 나오는 것을 확인할 수 있다.

4. 값 삭제

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

# 1.
list.remove();
# 2.
list.remove(1);
# 3.
list.removeFirst();
# 4.
list.removeLast();
# 5.
list.clear();

값 삭제 역시 기본적으로는 remove를 사용하여 가능하다.

예시 1번처럼 remove() 괄호 안의 인덱스 값을 생략하면 0번째 index의 value값을 제거한다.
예시 2번은 index자리에 1이 왔으니 index 1의 데이터 값을 제거했을 것이다.
removeFirst()를 사용하면 가장 앞의 데이터를 제거한다.
removeLast()를 사용하면 가장 뒤의 데이터를 제거한다.
예시 5번처럼 .clear()를 사용하면 모든 데이터를 지운다. (= 초기화 방법)

5. Linked List 크기 및 값 검색

- Linked List 크기

<예시>
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5));
System.out.println(list.size());)

Linked List의 크기는 size()로 구할 수 있다.
예시에서 list에는 1,2,3,4,5의 데이터가 들어가 있으므로 size를 출력하면 5이 나온다.

- Linked List 값 검색

ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,3));
# 1.
System.out.println(list.contains(1));
# 2.
System.out.println(list.indexOf(2)); //1이 있는 index반환 없으면 -1

Linked List에서 값 검색은 contains()와 indexOf()함수를 통해 확인할 수 있다.

contains(value)는 해당 value값이 있는지 검색해주는 것으로, 값이 있으면 true를 반환한다.
예시에서는 1을 검색했고, 값이 존재하므로 true를 반환했을 것이다.

indexOf(value)는 해당 value값이 있는 index를 반환해준다. 값이 없으면 -1을 반환한다.
예시에서는 2를 검색했고, 값이 존재하므로 2의 index인 1을 반환했을 것이다.

Reference

linked list
: https://st-lab.tistory.com/142
이미지 출처
: https://psychoria.tistory.com/767

++) 참고하여 공부하고 추가할 ref
https://st-lab.tistory.com/169?category=856997