노드(데이터 + 다음 노드 주소)를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
장점 | 단점 |
노드 (추가, 삭제)시간복잡도가 O(1) 입니다. | 노드 (탐색) 시간복잡도가 O(n) 입니다. |
문제 1: O(1) 이란 어느 정도의 시간복잡도 인지?
문제 2: O(n) 이란 어느 정도의 시간복잡도 인지?
- 단일 연결 리스트
- 이중 연결 리스트
- 원형 연결 리스트
단일 연결리스트란?
- 탐색을 우측으로 가는 단방향 탐색만 가능합니다.
- 단점으로 마지막 노드에서 좌측으로 탐색하는 역방향 탐색이 불가능합니다.
- Data Field : 데이터
- Link field : 다음 노드의 주소
class LinkedList<T> {
private ListNode head = null;
public void insert(ListNode preNode, T data) {
preNode.link = new ListNode<>(data, preNode.link);
}
public void insert(T data) {
ListNode<T> newNode = new ListNode<>(data, null);
if (head == null) {
this.head = newNode;
} else {
ListNode tempNode = head;
while (tempNode.link != null) {
tempNode = tempNode.link;
}
tempNode.link = newNode;
}
}
public void delete(T data) {
ListNode preNode = head;
ListNode tempNode = head.link;
if (data.equals(preNode.getData())) { //삭제하려는 데이터와 현재 노드 데이터와 일치하는 경우
head = preNode.link;
preNode.link = null;
} else {
while (tempNode != null) {
if (data.equals(tempNode.getData())) {
if (tempNode.link == null) {
preNode.link = null;
} else {
preNode.link = tempNode.link;
tempNode.link = null;
}
break;
} else {
preNode = tempNode;
tempNode = tempNode.link;
}
}
}
}
public void lastDelete() {
ListNode preNode;
ListNode tempNode;
if (head == null) {
return;
}
if (head.link == null) {
head = null;
} else {
preNode = head;
tempNode = head.link;
while (tempNode.link != null) {
preNode = tempNode;
tempNode = tempNode.link;
}
preNode.link = null;
}
}
public ListNode search(T data) {
ListNode tempNode = this.head;
while (tempNode != null) {
if (data == tempNode.getData()) {
return tempNode;
} else {
tempNode = tempNode.link;
}
}
return tempNode;
}
public void print() {
ListNode tempNode = this.head;
while (tempNode != null) {
System.out.print(tempNode.getData() + " ");
tempNode = tempNode.link;
}
}
}
- 우측 탐색만 가능한 단방향 탐색과는 달리 양방향 탐색이 가능합니다.
- Data Field : 데이터
- Next Link field : 다음 노드의 주소
- Prev Link field : 이전 노드의 주소
- 단일 연결리스트와 동일한 구조에서 아래와 같이 변경되었습니다.
1. Head가 사라지고 Tail이 추가되었습니다.
2. 마지막 노드가 첫 노드를 가르킵니다.
- Data Field : 데이터
- Link field : 다음 노드의 주소
- Tail : 마지막 노드
* 삽입,삭제가 단일 연결 리스트와 동일한 구조로 그림은 생략 되었습니다.
[자료구조] 트리 (Tree) (0) | 2020.11.05 |
---|---|
[자료구조] 덱 (Deque) (0) | 2020.11.05 |
[자료구조] 큐(Queue) (0) | 2020.11.05 |
[자료구조] 스택 (Stack) (0) | 2020.11.05 |
[자료구조] 자료구조란? (0) | 2020.11.01 |