1. 링크드 리스트 (Linked List) 구조
- 연결 리스트라고도 함
- 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
- 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
기본 구조와 용어
- 노드(Node) : 데이터 저장 단위 (데이터값, 포인터)로 구성
- 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
| 데이터 | 다음 데이터 주소 | ---> | 데이터 | 다음 데이터 주소 | ---> | 데이터 | 다음 데이터 주소 |
2. 간단한 링크드 리스트 예
- Node 구현
public class Node {
private Integer data;
public Node next;
public Node(Integer data) {
this.data = data;
this.next = null;
}
public Node(Integer data, Node next) {
this.data = data;
this.next = next;
}
public Integer getData() {
return this.data;
}
}
- Node와 Node 연결하기 (포인터 활용)
Node node1 = new Node(1);
Node node2 = new Node(2);
node1.next = node2;
Node head = node1;
- 링크드 리스트로 데이터 추가하기
public void add(Integer data) {
Node node = head;
while (node.next != null) {
node = node.next;
}
node.next = new Node(data);
}
- 링크드 리스트 데이터 출력하기(검색하기)
Node node = head;
while (node.next != null) {
System.out.println(node.getData());
node = node.next;
}
System.out.println(node.getData());
3. 링크드 리스트의 장단점
- 장점
- 미리 데이터 공간을 할당하지 않아도 됨 (배열은 미리 데이터 공간을 할당 해야 함)
- 단점
- 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
- 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
4. 링크드 리스트의 복잡한 기능1 (링크드 리스트 데이터 사이에 데이터를 추가)
- 링크드 리스트는 유지 관리에 부가적인 구현이 필요함
Node node1 = new Node(1);
Node node3 = new Node(3);
node1.next = node3;
Node head = node1;
Node node2 = new Node(2);
Node node = head;
Boolean search = true;
while (search) {
if (node.getData() == 1) {
search = false;
} else {
node = node.next;
}
}
Node node_next = node.next;
node.next = node2;
node2.next = node_next;
5. 링크드 리스트의 복잡한 기능2 (특정 노드를 삭제)
- head 삭제
- 마지막 노드 삭제
- 중간 노드 삭제
6. 링크드 리스트 구현하기
public class Node {
private Integer data;
public Node next;
public Node(Integer data) {
this.data = data;
this.next = null;
}
public Node(Integer data, Node next) {
this.data = data;
this.next = next;
}
public Integer getData() {
return this.data;
}
}
public class NodeMgmt() {
private Node head;
public void init(Integer data) {
head = new Node(data);
}
public void add(Integer data) {
if (head == null) {
head = new Node(data);
} else {
Node node = head;
while (node.next != null) {
node = node.next;
}
node.next = new Node(data);
}
}
public void desc() {
Node node = head;
while (node != null) {
System.out.println(node.getData());
node = node.next;
}
}
public void delete(Integer data) {
if (head == null) {
System.out.println("해당 값을 가진 노드가 없습니다.");
return;
}
// 1. head 삭제
if (head.getData() == data) {
head = head.next;
} else {
Node node = head;
while (node.next != null) {
// 2. 중간, 마지막 노드 삭제
if (node.next.getData() == data) {
Node temp = node.next;
node.next = node.next.next;
temp = null;
ruturn;
} else {
node = node.next;
}
}
}
}
public Node searchNode(Integer data) {
Node node = head;
while (node != null) {
if (node.getData() == data) {
return node;
} else {
node = node.next;
}
}
}
}
7. 다양한 링크드 리스트 구조
더블 링크드 리스트 (Double Linked List) 기본 구조
- 이중 연결 리스트라고도 함
- 장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
| 이전 데이터 주소 | 데이터 | 다음 데이터 주소 | ---> <--- |
이전 데이터 주소 | 데이터 | 다음 데이터 주소 |
public class Node {
public Node prev;
private Integer data;
public Node next;
public Node(Integer data) {
this.prev = null;
this.data = data;
this.next = null;
}
}
public class NodeMgmt() {
private Node head;
private Node tail;
public void init(Integer data) {
head = new Node(data);
tail = head;
}
public void insert(Integer data) {
if (head == null) {
head = new Node(data);
tail = head;
} else {
Node node = head;
while (node.next != null) {
node = node.next;
}
Node newNode = new Node(data);
node.next = newNode;
newNode.prev = node;
tail = newNode;
}
}
public void desc() {
Node node = head;
whild (node != null) {
System.out.println(node.getData());
node = node.next;
}
}
public Node searchFromHead(Integer data) {
if (head == null) {
return null;
}
Node node = head;
while (node != null) {
if (node.getData() == data) {
return node;
} else {
node = node.next;
}
}
return null;
}
public Node searchFromTail(Integer data) {
if (head == null) {
return null;
}
Node node = tail;
while (node != null) {
if (node.getData() == data) {
return node;
} else {
node = node.prev;
}
}
return null;
}
// 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수
public Boolean insertBefore(Integer data) {
if (head == null) {
head = new Node(data);
return true;
} else {
Node node = tail;
while (node.getData() != data) {
node = node.prev;
if (node == null) {
return false;
}
}
Node newNode = new Node(data);
newNode.prev = node.prev;
node.prev.next = newNode;
newNode.prev = node.prev;
newNode.next = node;
node.prev = newNode;
return true;
}
}
}