1.
링크드 리스트(Linked List) 구조
•
연결 리스트라고도 함
•
배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
•
링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
•
링크드 리스트 기본구조와 용어
◦
노드(Node) : 데이터 저장 단위(데이터 값, 포인터)로 구성
◦
포인터 : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
2.
간단한 링크드 리스트 예
•
최대한 간단한 형태로 코드로 작성해보며 링크드 리스트를 이해해 보기
2.1 Node 클래스 구현
public class Node<T> {
T data;
Node<T> next = null;
public Node(T data) {
this.data = data;
}
}
Java
복사
2.2 Node와 Node 연결하기 : Node 인스턴스간 연결
Node<Integer> node1 = new Node<Integer>(1);
Node<Integer> node2 = new Node<Integer>(2);
Java
복사
node1.next = node2;
Node<Integer> head = node1; // 정확히는 Node<Integer> 가 더 맞기 때문에 변경함
Java
복사
2.3 링크드 리스트에 데이터 추가하기
public class SingleLinkedList<T> {
public Node<T> head = null;
public class Node<T> {
T data;
Node<T> next = null;
public Node(T data) {
this.data = data;
}
}
public void addNode(T data) {
if (head == null) {
head = new Node<T>(data);
} else {
Node<T> node = this.head;
while (node.next != null) {
node = node.next;
}
node.next = new Node<T>(data);
}
}
}
Java
복사
SingleLinkedList<Integer> MyLinkedList = new SingleLinkedList<Integer>();
MyLinkedList.addNode(1);
Java
복사
MyLinkedList.head.data
Java
복사
MyLinkedList.addNode(2);
Java
복사
MyLinkedList.head.next.data
Java
복사
2.4 링크드 리스트 데이터 출력하기
public class SingleLinkedList<T> {
public Node<T> head = null;
public class Node<T> {
T data;
Node<T> next = null;
public Node(T data) {
this.data = data;
}
}
public void addNode(T data) {
if (head == null) {
head = new Node<T>(data);
} else {
Node<T> node = this.head;
while (node.next != null) {
node = node.next;
}
node.next = new Node<T>(data);
}
}
public void printAll() {
if (head != null) {
Node<T> node = this.head;
System.out.println(node.data);
while (node.next != null) {
node = node.next;
System.out.println(node.data);
}
}
}
}
Java
복사
SingleLinkedList<Integer> MyLinkedList = new SingleLinkedList<Integer>();
MyLinkedList.addNode(1);
MyLinkedList.addNode(2);
MyLinkedList.addNode(3);
MyLinkedList.printAll();
Java
복사
3.
링크드 리스트의 장단점(전통적인 C언어에서의 배열과 링크드 리스트)
•
장점
◦
미리 데이터 공간을 미리 할당하지 않아도 됨
▪
배열은 미리 데이터 공간을 할당
•
단점
◦
연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
◦
연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
◦
중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야하는 부가적인 작업 필요