[Java/자료구조] 선형구조 - 연결 리스트 이해하기 : 단순, 이중, 순환 연결리스트

반응형

해당 글에서는 자료구조에서 선형 구조 중 연결 리스트에 대해 알아봅니다.

 

 

 

💡 [참고] 자료구조론 구조

- 선형구조 중 연결리스트와 종류인 단순, 이중, 순환 연결 리스트를 확인해 봅니다. 

 

 

 

1) 선형 구조(Linear Structure)

---

 💡 선형 구조(Linear Structure)란?

- 데이터를 저장하기 위한 기본적인 형태로 데이터가 '일렬로 나열'되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미합니다.

- 선형 구조에는 순차 리스트, 연결 리스트, 큐(Queue), 스택(Stack), 덱(deque)이 있습니다.

 

https://goodgid.github.io/DS-Linear-and-NonLinear/

 

 

💡 [참고] 이외에 선형구조에 대해 궁금하시면 아래의 글을 참고하시면 도움이 됩니다

[Java/자료구조] 선형 구조 - 순차 리스트(Sequential List) 이해하기 : Array, ArrayList

[Java/자료구조] 선형구조 이해하기 -1 : 큐(Queue), 스택(Stack), 덱(Deque)

[Java/자료구조] 스택(Stack)/큐(Queue) 이해하기 -2 : 문제로 이해하기

[Java/자료구조] 선형구조 - 큐(Queue) 이해하기: 일반 큐, 우선순위 큐(Priority Queue) 이해하기

 

 

 

 

2) 연결 리스트(Linked List)

---

💡 연결 리스트(Linked List)

- 데이터 요소를 ‘노드(Node)’로 구성된 선형 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 링크(포인터)로 이루어져 있습니다.

- 연결 리스트는 동적 크기 조정이 용이하고, 삽입과 삭제가 빠르게 이루어질 수 있는 장점이 있습니다.
- 하지만 특정 위치에 접근하는 데에는 선형적인 탐색이 필요하기 때문에 접근 속도가 느릴 수 있습니다.
- 주로 데이터의 삽입과 삭제가 빈번하게 일어나는 상황에서 주로 사용됩니다. 큐(Queue)나 스택(Stack)과 같은 자료구조를 구현할 때 많이 활용됩니다. 또한 데이터 크기가 동적으로 변환하는 상황에서 유용하게 사용됩니다.

https://www.geeksforgeeks.org/what-is-linked-list/

 

 

[ 더 알아보기 ]

💡 링크(포인터)

- 연결 리스트에서 각 노드가 다음 노드를 가리키는 역할을 합니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있으며, 이를 통해 노드들이 서로 연결되어 선형 자료구조를 형성합니다.
- 링크(포인터)를 통해 다음 노드를 가리키기 때문에, 연결 리스트는 동적 크기 조정이 용이하고 빠른 삽입과 삭제가 가능합니다. 하지만 특정 위치에 접근하는 데에는 선형적인 탐색이 필요하기 때문에 접근 속도가 느릴 수 있습니다.


💡 선형 탐색 시간이란?

- 입력 크기에 비례하여 실행 시간이 증가하는 것을 의미합니다. 즉, 연결 리스트에서 특정 위치에 있는 요소에 접근하는 작업은 요소의 개수에 따라 시간이 선형적으로 증가합니다. 따라서 요소의 개수가 많을수록 접근 시간도 늘어날 수 있습니다.

 

 

 

1. LinkedList 특징

---

💡 연결 리스트 특징

1. 데이터 요소들이 노드(Node)들로 구성됩니다.

- 각 노드는 데이터와 다음 노드를 가리키는 포인터(참조)로 이루어져 있습니다.


2. 연결 리스트는 동적으로 크기가 조정될 수 있습니다.

- 요소의 추가나 삭제에 따라 리스트의 크기가 증가하거나 감소할 수 있습니다.


3. 삽입과 삭제 연산이 상대적으로 효율적입니다.

- 일반적으로 연결 리스트의 시작 또는 끝에 요소를 추가하거나 삭제하는 작업은 상수 시간에 이루어집니다. 하지만 특정 위치에 있는 요소에 접근하려면 포인터를 따라가야 하므로 선형 시간이 걸립니다.


4. 조회 시간이 상대적으로 시간이 걸립니다.

- 하나는 특정 위치에 있는 요소에 접근하는 것이 선형 시간이 걸린다는 것입니다. 따라서 조회 작업은 효율적이지 않을 수 있습니다.


5. 연결 리스트는 메모리를 효율적으로 사용할 수 있습니다.

- 각 노드는 필요한 만큼의 메모리를 차지하고, 요소의 추가 또는 삭제에 따라 메모리를 동적으로 할당하거나 해제할 수 있습니다.

 

 [더 알아보기]

💡 왜 LinkedList는 조회 속도가 느린걸까?

- 포인터를 따라가야 하기 때문에 느립니다. 각 노드는 다음 노드를 가리키는 포인터를 가지고 있으며, 특정 위치의 요소에 접근하려면 해당 위치까지 포인터를 따라가야 합니다. 이러한 과정은 연결 리스트의 길이에 비례하여 시간이 걸리기 때문에 접근 시간이 길어집니다.

 

 

 

 

2. LinkedList 활용 : List, LinkedList 인터페이스를 사용한 차이

---

💡 List, LinkedList 인터페이스를 사용한 차이

💡 List 인터페이스를 사용한 경우

- 컬렉션 프레임워크의 List 인터페이스를 구현하는 모든 클래스의 객체로 처리할 수 있습니다. List 인터페이스는 공통으로 구현된 메서드 집합을 제공합니다.

💡 LinkedList 인터페이스를 사용하는 경우

- 컬렉션 프레임워크의 LinkedList 인터페이스에서 제공하는 특정 메서드와 기능에 액세스 하고 사용할 수 있습니다.

// List 인터페이스를 이용한 LinkedList 구현체 구성
List<String> strList = new LinkedList<>();

// LinkedList 인터페이스를 이용한 LinkedList 구현체 구성
LinkedList<String> strLinkedList = new LinkedList<>();

 

 

 

3.  시간복잡도

---

💡 시간 복잡도(Time Complexity)

- 알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 효율적인 알고리즘을 나타내는 척도를 의미합니다.
- 즉, 입력 값이 커질수록 알고리즘의 수행 시간이 어떻게 증가하는지에 따른 지표입니다.

- O(1) : 상수 시간 → O(log n) : 로그 시간 → O(n) : 선형 시간 → O(n log n) : 선형 로그 시간 → O(n^2) : 이차 시간 → O(2^n) : 지수 시간 → O(n!) : 팩토리얼 시간 순입니다.

연산	ArrayList	단순 연결 리스트	이중 연결 리스트	순환 연결 리스트
조회	O(1) : 상수 시간	O(n) : 선형 시간	O(n) : 선형 시간	O(n) : 선형 시간
삽입, 삭제	최악의 경우 O(n) : 선형 시간 평균적으로 O(n/2)	O(1) : 상수 시간	O(1) : 상수 시간	O(1) : 상수 시간
리스트 전체 순회	O(n): 선형 시간	O(n) : 선형 시간	O(n) : 선형 시간	O(n) : 선형 시간

 

[Java/알고리즘] 시간 복잡도, 공간 복잡도, 빅오 표기법 이해하기

 

 

 

 

 

 

 

 

3) 연결 리스트 종류 : 단순 연결 리스트(Singly Linked List)

---

💡 단순 연결 리스트(Singly Linked List)

- 데이터 요소인 노드들이 ‘링크’로 연결되어 있는 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 링크로 이루어져 있습니다.

- 단순 연결 리스트는 ‘데이터의 삽입과 삭제가 빠르며 메모리 공간을 효율적으로 사용’할 수 있습니다. 삽입 또는 삭제하는 경우에는 단순히 링크를 변경하면 되므로, 배열과 같은 다른 데이터 구조에서 발생하는 데이터 이동이 필요하지 않습니다.
- 그러나 데이터의 검색에는 선형적인 탐색이 필요하므로 효율성이 떨어질 수 있습니다. 특정 위치의 요소에 접근하기 위해서는 ‘헤드부터 순차적으로 탐색’ 해야 한다는 단점이 있습니다.
- 많은 알고리즘과 데이터 구조에서 사용되며, 데이터의 동적 할당과 해제에 유용합니다. 또한, 스택(Stack)이나 큐(Queue)와 같은 다른 추상 자료형을 구현하는 데에도 활용됩니다.

 

 

 

 

 

4) 연결 리스트 종류: 이중 연결 리스트(Doubly Linked List)

---

 💡 이중 연결 리스트(Double Linked List)

- 각 노드가 이전 노드와 다음 노드를 모두 가리키는 링크로 이루어져 있는 자료구조입니다. 양방향으로 탐색이 가능하며, 어떤 위치의 노드에서도 앞과 뒤의 노드에 접근할 수 있습니다.

- 이중 연결 리스트는 단순 연결 리스트와 달리 양방향으로 순회할 수 있으며, 양쪽 방향에서의 삽입과 삭제가 가능합니다. 이는 데이터의 검색과 수정을 효율적으로 처리할 수 있는 장점을 제공합니다.
- 그러나 각 노드가 이전 노드와 다음 노드를 가리키는 링크를 유지해야 하므로, 메모리 사용량이 증가하게 됩니다.
- 이중 연결 리스트는 데이터의 삽입 및 삭제 작업이 빈번하게 발생하는 상황에서 유용하게 사용됩니다. 또한, 이중 연결 리스트를 기반으로 구현된 많은 알고리즘과 데이터 구조가 존재하며, 예를 들어 LRU Cache와 같은 자료구조에서 활용됩니다.

https://www.geeksforgeeks.org/introduction-and-insertion-in-a-doubly-linked-list/

 

 

 

5) 연결 리스트 종류: 순환 연결 리스트(Circular Linked List)

---

💡 순환 연결 리스트(Circular Linked List)

- 마지막 노드가 첫 번째 노드를 가리키는 형태로 이루어져 있는 자료구조입니다. 즉 리스트가 끝에서 시작으로 연결되는 원형 구조를 가지고 있습니다. 이러한 특성으로 인해 마지막 노드의 다음 노드가 첫 번째 노드가 되며, 첫 번째 노드의 이전 노드가 마지막 노드가 됩니다.

- 순환 연결 리스트는 데이터의 삽입과 삭제를 빠르게 처리할 수 있는 장점이 있습니다. 또한, 리스트의 시작과 끝이 연결되어 있으므로 순환 구조를 이용한 다양한 알고리즘을 구현할 수 있습니다.
- 그러나 순환 연결 리스트를 순회하는 경우 무한 루프에 빠질 수 있으므로 조심해야 합니다.
- 순환 연결 리스트는 리스트의 순서를 계속해서 이동하면서 작업을 수행해야 하는 경우에 유용합니다. 예를 들어, 원형 큐(Circular Queue)나 원형 버퍼(Circular Buffer)와 같이 순환적인 동작이 필요한 자료 구조에서 사용됩니다. 또한, 순환 연결 리스트는 알고리즘에서 반복적인 동작을 처리하는 데에도 활용될 수 있습니다.

 

https://www.geeksforgeeks.org/circular-linked-list/

 

 

 

 

 

 

6) 연결 리스트 활용하기 : 함수를 이용한 활용방안

---

💡 [참고] LinkedList 메서드에 대해 API 문서를 기반으로 작성하였습니다.

[Java/API] LinkedList Method API Document : Java 11

 

 

1. LinkedList 요소 조회

---

💡 LinkedList 요소 조회

- LinkedList내의 요소를 추가 방법으로 getFirst(), get(), getLast() 함수를 활용하여 확인해 봅니다.

 

 

1.1. LinkedList 첫 번째 요소 조회 : getFirst()

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. 첫번째 값 조회
String firstVal = linkedList.getFirst();

System.out.println("linkedList :: " + firstVal); // linkedList :: A

 

 

 

1.2. LinkedList 조회 : get()

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. 첫번째 값 조회
String item = linkedList.get(1);

System.out.println("linkedList :: " + item); // linkedList :: B

 

 

 

1.3. LinkedList 마지막 요소 조회 : getLast()

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. 첫번째 값 조회
String lastVal = linkedList.getLast();

System.out.println("linkedList :: " + lastVal); // linkedList :: D

 

 

 

 

2. LinkedList 요소 추가

---

💡 LinkedList 요소 추가

- LinkedList내의 요소를 추가 방법으로 addFirst(), add(), addLast() 함수를 활용하여 확인해 봅니다.

 

 

 

2.1. 단순 연결 리스트 첫 번째 요소 추가 : addFirst()

💡 단순 연결 리스트 첫 번째 요소 추가

- LinkedList 내에 A, B, C, D가 존재할 시 E라는 값을 ‘가장 앞’에 추가합니다.
- 이를 위해서 Head로 연결되어 있는 부분을 제거하고 E에 Head를 연결합니다..

 

https://www.geeksforgeeks.org/insertion-in-linked-list/

 

 

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. LinkedList 첫번째 값 추가
linkedList.addFirst("E");

System.out.println("linkedList :: " + linkedList); // linkedList :: [E, A, B, C, D]

 

 

 

 

2.2. 단순 연결 리스트 중간 요소 추가 : add()

💡 단순 연결 리스트 중간 요소 추가

- LinkedList 내에 A, B, C, D가 존재할 시 E라는 값을 중간에 추가합니다.
- 이를 위해서 B→C의 노드를 끊고 추가를 E를 추가하여 연결을 해줍니다.

 

https://www.geeksforgeeks.org/insertion-in-linked-list/

 

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. LinkedList B 다음에 값을 넣습니다.
int index = linkedList.indexOf("B");
linkedList.add(index + 1, "E");

System.out.println("linkedList :: " + linkedList); // linkedList :: [A, B, E, C, D]

 

 

 

2.3. 단순 연결 리스트 마지막 요소 추가 : addLast()

💡 LinkedList 추가: 마지막 요소에 추가

- LinkedList 내에 A, B, C, D가 존재할 시 E라는 값을 ‘가장 뒤’에 추가합니다.
- D에서 Null의 연결을 끊고 E로 이어주고 E 뒤에 노드를 NULL로 연결합니다.

https://www.geeksforgeeks.org/insertion-in-linked-list/

 

 

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. LinkedList 마지막 값 추가
linkedList.addLast("E");

System.out.println("linkedList :: " + linkedList); // linkedList :: [A, B, C, D, E]

 

 

 

3. LinkedList 요소 수정

---

 

💡 LinkedList 요소 수정

- LinkedList 내의 요소를 ‘수정’ 방법으로 set() 함수를 활용하여 확인해 봅니다.

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

linkedList.set(0, "1");
linkedList.set(1, "2");
linkedList.set(2, "3");
linkedList.set(3, "4");
System.out.println("linkedList :: " + linkedList); // linkedList :: ["1", "2", "3", "4"];

 

 

 

 

4. LinkedList 요소 삭제

---

💡 LinkedList 요소 삭제

- LinkedList내의 요소를 ‘삭제’ 방법으로 removeFirst(), remove(), removeLast() 함수를 활용하여 확인해 봅니다.

 

4.1. LinkedList 첫 번째 요소 삭제 : removeFirst()

💡 LinkedList 첫 번째 요소 삭제

- removeFirst() 메서드를 사용하여 Head와 “A”간의 연결되어 있는 링크를 끊어주고 Head와 “B”의 링크를 이어줍니다.

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. 첫번째 요소 제거
linkedList.removeFirst();
System.out.println("linkedList :: " + linkedList); // linkedList :: ["B", "C", "D"];

 

 

 

 

4.2. LinkedList 중간 요소 삭제 : remove()

💡 LinkedList 중간 요소 삭제

- remove() 메서드를 사용하여 index값을 기반하여 “C”를 찾아서 연결을 끊어주고 “B”→”D”를 연결해 줍니다.

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. "C" 요소 제거 
linkedList.remove(2);
System.out.println("linkedList :: " + linkedList); // linkedList :: ["A", "B", "D"];

 

 

 

4.3. LinkedList 마지막 요소 삭제 : removeLast()

💡 LinkedList 마지막 요소 삭제

- removeLast() 메서드를 사용하여 "D"와 NULL 간의 연결되어 있는 링크를 끊어주고 "C"와 NULL의 링크를 이어줍니다.

// 1. LinkedList 초기화 + 값 할당
LinkedList<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 2. 마지막 요소 제거
linkedList.removeLast();
System.out.println("linkedList :: " + linkedList); // linkedList :: ["A", "B", "C"];

 

 

 

💡[참고] 좀 더 다양한 자료구조에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.

분류	주제	링크
선형구조	순차 리스트(Array, ArrayList)	https://adjh54.tistory.com/317
선형구조	연결 리스트(단순, 이중, 순환 리스트)	https://adjh54.tistory.com/319
선형구조	큐, 스텍, 덱	https://adjh54.tistory.com/135
선형구조	큐, 스텍, 덱 (문제로 이해하기)	https://adjh54.tistory.com/185
선형구조	큐(일반 큐, 우선순위 큐)	https://adjh54.tistory.com/226
비선형구조	트리(일반트리/이진트리)	https://adjh54.tistory.com/320
비선형구조	균형트리(AVL, 레드-블랙, B-트리)	https://adjh54.tistory.com/324
비선형구조	그래프(방향, 무방향 그래프)	https://adjh54.tistory.com/325

 

 

 

 

 

 

오늘도 감사합니다. 😀