![[자료구조] 연결리스트](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FYZ8Ps%2FbtrJgxBD41E%2FLErPpSYNbRcQVFFncKWfzk%2Fimg.png)
728x90
연결리스트 (LinkedList)란?
- 데이터를 링크로 연결해서 관리하는 자료구조
- 기본 구조 : 노드 ( 값 + 포인터 )
- 자료의 순서는 정해져 있지만, 메모리 상 연속성이 보장되지는 않음
<장점>
1. 데이터 공간을 미리 할당할 필요 없다.
2. 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제가 용이하다.
<단점>
1. 연결 구조를 위한 별도의 데이터 공간이 필요 -> 상대적 느림
2. 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요!
[ 데이터 추가 ]
추가할 데이터를 담을 노드 생성
↓
링크 연결 작업
↓
head 이전 작업 (제일 앞으로)
[ 데이터 삭제 ]
삭제 대상 노드 지정
↓
head 이전 작업
↓
delete_node 삭제 ( 링크도 함께 삭제해주기 )
유형1. 단순 연결 리스트
- 연결 리스트에 데이터 추가
- before_data가 null인 경우, 가장 뒤에 추가
- before_data가 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
더보기
class Node {
int data;
Node next;
Node() {}
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
LinkedList() {}
LinkedList(Node node) {this.head = head;}
// 연결 리스트 비어있는지 확인
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}
// 연결리스트 맨 뒤에 데이터 추가
public void addData(int data) {
if (this.head == null) {
this.head = new Node(data, null); // 새로운 노드가 헤드 됨
} else {
Node cur = this. head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
}
}
// 연결리스트의 맨 뒤의 데이터 삭제
public void removeData() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node prev = cur;
while (cur.next != null) {
prev = cur;
cur = cur.next;
}
if (cur == this.head) {
this.head = null;
} else {
prev.next = null;
}
}
// 연결리스트에서 데이터 찾기
public void findData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
while (cur != null) {
if (cur.data == data) {
System.out.println("Data Exist !");
return;
}
cur = cur.next;
}
System.out.println("Data not Found!");
}
// 연결리스트의 모든 데이터 출력
public void showData() {
if (this.isEmpty()) {
System.out.println("List is Empty!");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
유형2. 양방향 연결 리스트
- 단방향 연결리스트와 달리, (prev + next) 총 2개의 노드를 갖는다.
- 데이터 추가 / 삭제 시, head인지만 확인하면 안되고, head / tail 여부를 함께 확인해야한다.
- 특히, 데이터를 삭제할 때 Node도 함께 null 값으로 바꿔주어야한다.
더보기
class NodeBi {
int data;
NodeBi next;
NodeBi prev;
NodeBi(int data, NodeBi next, NodeBi prev) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
class DoublyLinkedList extends LinkedList {
NodeBi head;
NodeBi tail;
DoublyLinkedList(NodeBi node) {
this.head = node;
this.tail = node;
}
// 연결 리스트 비어있는지 확인
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}
// 연결 리스트에 데이터 추가
// before_data 가 null 인 경우, 가장 뒤에 추가
// before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData) {
if (this.head == null) {
this.head = new NodeBi(data, null, null);
this.tail = this.head;
} else if (beforeData == null) {
this.tail.next = new NodeBi(data, null, this.tail);
this.tail = this.tail.next;
} else {
NodeBi cur = this.head;
NodeBi pre = cur;
while (cur != null) {
if (cur.data == beforeData) {
if (cur == this.head) {
this.head = new NodeBi(data, this.head, null);
this.head.next.prev = this.head;
} else {
pre.next = new NodeBi(data, cur, pre);
cur.prev = pre.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
}
// 연결 리스트에서 특정 값을 가진 노드 삭제
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head && cur == this.tail) {
this.head = null;
this.tail = null;
} else if (cur == this.head) {
this.head = cur.next;
this.head.prev = null;
} else if (cur == this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
}
}
// 연결 리스트의 모든 데이터 출력
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty!");
return;
}
NodeBi cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
// 연결 리스트의 모든 데이터 출력 (tail 부터)
public void showDataFromTail() {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur = this.tail;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.prev;
}
System.out.println();
}
}
유형3. 원형 연결 리스트
- 이전의 연결리스트들은 마지막 노드가 NULL을 가리킴
- 원형 연결리스트의 경우, 마지막 노드가 첫 번째 노드를 가리킨다.
- 사실 상, 머리와 꼬리의 구분이 없다고 생각하면 된다.
더보기
class CircularLinkedList {
NodeBi head;
NodeBi tail;
CircularLinkedList(NodeBi node) {
this.head = node;
this.tail = node;
node.next = this.head;
node.prev = this.head;
}
public boolean isEmpty() {
if (this.head == null) {
return true;
}
return false;
}
// 연결 리스트에 데이터 추가
// before_data 가 null 인 경우, 가장 뒤에 추가
// before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData) {
if (this.head == null) {
NodeBi newNodeBi = new NodeBi(data, null, null);
this.head = newNodeBi;
this.tail = newNodeBi;
newNodeBi.next = newNodeBi;
newNodeBi.prev = newNodeBi;
} else if (beforeData == null) {
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next= newNodeBi;
this.head.prev = newNodeBi;
this.tail = newNodeBi;
} else {
NodeBi cur = this.head;
NodeBi pre = cur;
do {
if (cur.data == beforeData) {
if (cur == this.head) {
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next = newNodeBi;
this.head.prev = newNodeBi;
this.head = newNodeBi;
} else {
NodeBi newNodeBi = new NodeBi(data, cur, pre);
pre.next = newNodeBi;
cur.prev = newNodeBi;
}
break;
}
pre = cur;
cur = cur.next;
} while (cur != this.head);
}
}
// 연결 리스트에서 특정 값을 가진 노드 삭제
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head && cur == this.tail) {
this.head = null;
this.tail = null;
} else if (cur == this.head) {
cur.next.prev = this.head.prev;
this.head = cur.next;
this.tail.next = this.head;
} else if (cur == this.tail) {
pre.next = this.tail.next;
this.tail = pre;
this.head.prev = this.tail;
} else {
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty!");
return;
}
NodeBi cur = this.head;
while (cur.next != this.head) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println(cur.data);
}
}728x90
'자료구조' 카테고리의 다른 글
| [자료구조] 데크 (0) | 2022.08.16 |
|---|---|
| [자료구조] 큐 (0) | 2022.08.13 |
| [자료구조] 스택 (0) | 2022.08.13 |
| [자료구조] 조합 (0) | 2022.08.08 |
| [자료구조] 순열 (0) | 2022.07.10 |