코딩테스트
[자료구조][이중 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 6
독고냥이
2024. 1. 26. 12:30
[이전 글]
2024.01.26 - [코딩테스트] - [자료구조][단일 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 5
[자료구조][단일 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 5
[이전 글] 2024.01.25 - [코딩테스트] - [자료구조][스택] 코딩테스트, 정보처리기사를 위한 기초 4 [자료구조][스택] 코딩테스트, 정보처리기사를 위한 기초 4 [이전 글] 2024.01.25 - [코딩테스트] - [자료
tokkoutai.tistory.com
- Linked List 란?
- 데이터의 집합을 나타내는 지료구조로, 각 데이터 요소를 노드(Node)라고 칭한다.
- 각 노드는 데이터 필드와 다음 노드를 가리키는 링크(포인터)로 구성
- 배열과 달리 메모리에 연속적으로 배치되지 않으며, 동적으로 크기가 조절된다.
- 주요 특징과 용어
- 노드(Node) : 데이터와 다음 노드를 가리키는 링크로 구성된 기본 단위
- 헤드(Head) : 링크드 리스트의 첫 번째 노드
- 테일(Tail) : 링크드 리스트의 마지막 노드 (일부 구현에서는 테일이 없는 경우도 있음)
- 링크(Link) : 각 노드가 다음 노드를 가리키는 참조
- 링크드 리스트의 종류
- 단일 연결 리스트 (Singly Linked List) : 각 노드가 다음 노드를 가리키는 구조
- 장점 : 구현이 간단하고 일반 배열의 단점(데이터 추가, 삭제)을 보완
- 단점 : 첫 노드 부터 다음 노드 순으로 순차적으로 노드를 찾아야 하는 구조여서 마지막 노드를 찾을 경우 느림
- 이중 연결 리스트 (Doubly Linked List) : 각 노드가 이전 노드와 다음 노드를 가리키는 구조
- 장점 : 단일 연결 리스트의 단점을 보완하여 양방향으로 노드를 연결하여 리스트 앞, 뒤로 탐색이 모두 가능
- 단점 : 메모리 공간을 단일 연결 리스트 보다 더 사용, 구현 복잡도 증가, 추가적인 연산 시간 복잡도
- 순환 연결 리스트 (Circular Linked List) : 마지막 노드가 첫 번째 노드를 가리키는 구조
- 단일 연결 리스트 (Singly Linked List) : 각 노드가 다음 노드를 가리키는 구조
- 이중 연결 리스트 예제
- 철수는 쉬는 시간이 시작 하자 마자 매점에 갔다. 첫번째로 도착한 철수는 1번으로 간식을 산다.
- 그 뒤로 수미가 왔고 순서대로 임정, 정희, 지웅이 줄을 섰다.
- 영이 는 뒤늦게 왔는데 수미 앞으로 세치기를 하고, 정희는 다른 일이 생겨 매점에서 나간다.
package linkedlist;
public class DoubleLinkedListTest {
public static class Node<T> {
T data;
Node<T> prev = null;
Node<T> next = null;
public Node(T data) {
this.data = data;
}
}
public static class DoubleLinkedList<T> {
public Node<T> head = null; // 첫번째 노드
public Node<T> tail = null; // 마지막 노드
public void addNode(T data) {
if (head == null) {
head = new Node<T>(data);
tail = head;
} else {
Node<T> node = this.head;
while (node.next != null) {
node = node.next;
}
node.next = new Node<T>(data);
node.next.prev = node;
this.tail = node.next;
}
}
public void printAll() {
if (head != null) {
Node<T> node = this.head;
printNode(node);
while (node.next != null) {
node = node.next;
printNode(node);
}
System.out.println();
}
}
private void printNode(Node<T> node) {
if (node.prev != null)
System.out.print("<prev:" + node.prev.data + ">");
else
System.out.print("<prev:" + null + ">");
System.out.print("[" + node.data + "]");
if (node.next != null)
System.out.println("<next:" + node.next.data + ">");
else
System.out.println("<next:" + null + ">");
}
/**
* 특정 노드 앞에 신규 노드 추가
*
* @param existedData : 기존 노드
* @param addData : 신규 노드
* @return
*/
public boolean insertToFront(T existedData, T addData) {
if (this.head == null) {
this.head = new Node<T>(addData);
this.tail = this.head;
} else if (this.head.data == existedData) {
Node<T> newHead = new Node<T>(addData);
newHead.next = this.head;
this.head = newHead;
return true;
} else {
Node<T> node = this.head;
while (node != null) {
if (node.data == existedData) {
Node<T> nodePrev = node.prev;
nodePrev.next = new Node<T>(addData);
nodePrev.next.next = node;
nodePrev.next.prev = nodePrev;
node.prev = nodePrev.next;
return true;
} else {
node = node.next;
}
}
}
return false;
}
public boolean removeNode(T data) {
if (head != null) {
Node<T> node = head;
if (node.data == data) {
this.head = this.head.next;
return true;
} else {
while (node.next != null) {
if (node.next.data == data) {
node.next = node.next.next;
node.next.prev = node;
return true;
}
node = node.next;
}
}
}
return false;
}
}
public static void main(String[] args) {
DoubleLinkedList<String> linkedList = new DoubleLinkedList<>();
linkedList.addNode("철수");
linkedList.addNode("수미");
linkedList.addNode("임정");
linkedList.addNode("정희");
linkedList.addNode("지웅");
linkedList.printAll();
System.out.println("> 수미 전에 영이 추가");
linkedList.insertToFront("수미", "영이");
linkedList.printAll();
System.out.println("> 정희 이탈");
linkedList.removeNode("정희");
linkedList.printAll();
}
}
/**
* [결과 값]
<prev:null>[철수]<next:수미>
<prev:철수>[수미]<next:임정>
<prev:수미>[임정]<next:정희>
<prev:임정>[정희]<next:지웅>
<prev:정희>[지웅]<next:null>
> 수미 전에 영이 추가
<prev:null>[철수]<next:영이>
<prev:철수>[영이]<next:수미>
<prev:영이>[수미]<next:임정>
<prev:수미>[임정]<next:정희>
<prev:임정>[정희]<next:지웅>
<prev:정희>[지웅]<next:null>
> 정희 이탈
<prev:null>[철수]<next:영이>
<prev:철수>[영이]<next:수미>
<prev:영이>[수미]<next:임정>
<prev:수미>[임정]<next:지웅>
<prev:임정>[지웅]<next:null>
*/
- 이중 연결 리스트 탐색 예제
- findNodeFromHead 메서드와 findNodeFromTail 메서드 추가
- findNodeFromHead 메서드는 노드 앞에서 부터 탐색 시작
- findNodeFromTail 메서드는 노드 뒤에서 부터 탐색 시작
package linkedlist;
public class DoubleLinkedListTest {
public static class Node<T> {
T data;
Node<T> prev = null;
Node<T> next = null;
public Node(T data) {
this.data = data;
}
}
public static class DoubleLinkedList<T> {
public Node<T> head = null; // 첫번째 노드
public Node<T> tail = null; // 마지막 노드
public void addNode(T data) {
if (head == null) {
head = new Node<T>(data);
tail = head;
} else {
Node<T> node = this.head;
while (node.next != null) {
node = node.next;
}
node.next = new Node<T>(data);
node.next.prev = node;
this.tail = node.next;
}
}
public void printAll() {
if (head != null) {
Node<T> node = this.head;
printNode(node);
while (node.next != null) {
node = node.next;
printNode(node);
}
System.out.println();
}
}
private void printNode(Node<T> node) {
if (node.prev != null)
System.out.print("<prev:" + node.prev.data + ">");
else
System.out.print("<prev:" + null + ">");
System.out.print("[" + node.data + "]");
if (node.next != null)
System.out.println("<next:" + node.next.data + ">");
else
System.out.println("<next:" + null + ">");
}
/**
* 특정 노드 앞에 신규 노드 추가
*
* @param existedData : 기존 노드
* @param addData : 신규 노드
* @return
*/
public boolean insertToFront(T existedData, T addData) {
if (this.head == null) {
this.head = new Node<T>(addData);
this.tail = this.head;
} else if (this.head.data == existedData) {
Node<T> newHead = new Node<T>(addData);
newHead.next = this.head;
this.head = newHead;
return true;
} else {
Node<T> node = this.head;
while (node != null) {
if (node.data == existedData) {
Node<T> nodePrev = node.prev;
nodePrev.next = new Node<T>(addData);
nodePrev.next.next = node;
nodePrev.next.prev = nodePrev;
node.prev = nodePrev.next;
return true;
} else {
node = node.next;
}
}
}
return false;
}
private Node<T> findNodeFromHead(T data) {
if (head != null) {
Node<T> node = this.head;
while (node != null) {
if (node.data.equals(data))
return node;
else
node = node.next; //앞에서 뒤로 이동
}
}
return null;
}
private Node<T> findNodeFromTail(T data) {
if (head != null) {
Node<T> node = this.tail;
while (node != null) {
if (node.data.equals(data))
return node;
else
node = node.prev; // 뒤에서 앞으로 이동
}
}
return null;
}
public boolean removeNode(T data) {
if (head != null) {
Node<T> node = head;
if (node.data == data) {
this.head = this.head.next;
return true;
} else {
while (node.next != null) {
if (node.next.data == data) {
node.next = node.next.next;
node.next.prev = node;
return true;
}
node = node.next;
}
}
}
return false;
}
}
public static void main(String[] args) {
//findNodeFromHead, findNodeFromTail test
System.out.println("\n> findNodeFromHead test 시작");
// 노드 추가 시작 시간 기록
long startTime = System.currentTimeMillis();
DoubleLinkedList<Integer> findNodeList = new DoubleLinkedList<>();
for (int i = 0; i < 200000; i++) {
findNodeList.addNode(i);
}
//노드 추가 경과 시간 기록
long endTime = System.currentTimeMillis();
//노드 추가 경과 시간 계산
long elapsedTime = (endTime - startTime) / 1000;
System.out.println("노드 추가 경과 시간 : " + elapsedTime + "초");
startTime = System.currentTimeMillis();
Node<Integer> node = findNodeList.findNodeFromHead(199999);
findNodeList.printNode(node);
//탐색 종료 시간 기록
endTime = System.currentTimeMillis();
//탐색 경과 시간 계산
double elapsedTime2 = (endTime - startTime) / 1000D;
//결과 출력
System.out.println("findNodeFromHead 탐색 실행 시간 : " + elapsedTime2 + "초");
System.out.println("\n> findNodeFromTail test 시작");
startTime = System.currentTimeMillis();
node = findNodeList.findNodeFromTail(199999);
findNodeList.printNode(node);
//탐색 종료 시간 기록
endTime = System.currentTimeMillis();
//탐색 경과 시간 계산
elapsedTime2 = (endTime - startTime) / 1000D;
//결과 출력
System.out.println("findNodeFromTail 탐색 실행 시간 : " + elapsedTime2 + "초");
}
}
/**
* [결과 값]
> findNodeFromHead test 시작
노드 추가 경과 시간 : 34초
<prev:199998>[199999]<next:null>
findNodeFromHead 탐색 실행 시간 : 0.002초
> findNodeFromTail test 시작
<prev:199998>[199999]<next:null>
findNodeFromTail 탐색 실행 시간 : 0.0초
*/