![[자료구조] LinkedList](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fc2UA3O%2FbtrtnD4bpIa%2FjYEsfQhTRUL5A32HxAKmX1%2Fimg.png)
LinkedList
- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조
- 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
- 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당
Linked List 특징
- ArrayList에 비해서 데이터의 추가나 삭제가 용이
- 미리 데이터 공간 할당하지 않아도 됨 (<-> 배열)
- 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어짐
- 배열은 index로 바로 찾음 -> 탐색, 정렬에 유리
- 연결을 위한 별도 데이터 공간 필요 → 저장공간 효율 떨어짐
LinkedList 직접 구현
class LinkedList<T> {
// head 노드 지정
public Node<T> head = null;
// Node 클래스
public class Node<T> {
T data;
Node<T> next = null; // 다음 노드를 가리키는 포인터
// 생성자
public Node(T data) {
this.data = data;
}
}
// LinkedList 맨 뒤에 데이터 추가하는 메서드
public void addNode(T data) {
// head 노드가 null이면
if(head == null) {
// 바로 head에 노드 생성
head = new Node<T>(data);
} else {
// null이 아니면 head를 node에 담아준다.
Node<T> node = this.head;
// node의 next가 null이 아니면 다음 노드가 있다는 뜻
// 다음 노드가 없을 때까지 현재 노드를 다음 노드로 바꿔주기
while (node.next != null) {
node = node.next;
}
// while문으로 끝 node까지 다 가면 그 다음 노드에 새로운 노드 생성
node.next = new Node<T>(data);
}
}
// 데이터 출력 메서드
public void printAll() {
if(head != null) {
// head 노드 node에 담기
Node<T> node = this.head;
// head 노드 출력
System.out.println(node.data);
// 노드 끝까지
while(node.next != null) {
// 다음 노드 지정
node = node.next;
// 값 출력
System.out.println(node.data);
}
}
}
// data 값 가지고 있는 node 찾기
public Node<T> search(T data) {
// head가 없으면 빈 LikedList
if(head == null) {
return null;
} else {
Node<T> node = this.head;
// 링크드 리스트의 끝까지 탐색
while (node != null) {
// 노드의 데이터를 찾은 경우
if(node.data == data) {
return node;
} else { // 못찾으면 다음 노드로 이동
node = node.next;
}
}
// 끝까지 돌려도 못찾았을 경우 head == null이 되니까 null 반환
return null;
}
}
public void addNodeInside(T data, T isData) {
// 먼저 isData 값을 가지고 있는 노드를 찾는다.
Node<T> searchedNode = this.search(isData);
// 리턴 받은 노드 객체가 null이면
if(searchedNode == null) {
// isData를 가지고 있는 노드가 없으므로 그냥 맨 마지막에 추가
this.addNode(data);
} else {
// 반환 받은 노드의 다음 노드를 nextNode에 담기
Node<T> nextNode = searchedNode.next;
// 리턴 받은 노드 다음 노드를 새로운 노드(data)로 설정(생성)
searchedNode.next = new Node<T>(data);
// 새로 만든 노드의 다음 노드를 기존 노드의 다음 노드로 지정
searchedNode.next.next = nextNode;
}
}
// 삭제 성공하면 true, 실패하면 null return
public boolean delNode(T isData) {
// head가 없으면 빈 LikedList
if (this.head == null) {
return false;
} else {
Node<T> node = this.head;
// head가 삭제할 노드라면
if (node.data == isData) {
// head의 다음 노드를 head로 지정
this.head = this.head.next;
return true;
} else {
// 노드 끝까지 탐색
while (node.next != null) {
// 다음 노드의 데이터가 삭제해야할 데이터라면
if (node.next.data == isData) {
// 노드의 다음 노드를 노드의 다음 다음 노드로 설정
node.next = node.next.next;
return true;
}
// 다음 노드로 이동
node = node.next;
}
// 노드의 끝까지 가도 삭제할 데이터가 없을 때 false 반환
return false;
}
}
}
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<Integer>();
list.addNode(1);
System.out.println(list.head.data); // 1
list.addNode(2);
System.out.println(list.head.next);// REPL.$JShell$25$SingleLinkedList$Node@47167d66 -> 노드 객체
System.out.println(list.head.next.data); // 2
list.addNodeInside(5, 1);
list.printAll(); // 1 5 2
list.delNode(5);
list.printAll(); // 1 2
}
}Doubly Linked List
- 실제 자바에서 제공하는 util 패키지의 LinkedList는 Doubly LinkedList랑 같은 형식
- 단일 Linked List에서 '이전 노드'를 가리키는 변수가 추가 된다.
- 단일 LinkedList는 head부터 찾아나가야 해서 오래걸렸는데 Doubly Linked List는 앞, 뒤 포인터 2개를 가지고 있어서 양방향으로 빠른 탐색이 가능하다
class DLinkedList<T> {
// 노드의 첫 부분
public Node<T> head = null;
// 노드의 마지막 부분
public Node<T> tail = null;
// 요소 개수
private int size;
// 초기화
public DLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
class Node<E> {
E data;
Node<E> next; // 다음 노드객체를 가리키는 래퍼런스 변수
Node<E> prev; // 이전 노드객체를 가리키는 래퍼런스 변수
Node(E data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// 노드의 끝에 데이터 추가하기
public void addNode(T data) {
if(this.head == null) {
this.head = new Node<T>(data);
this.tail = this.head;
} else {
Node<T> node = this.head;
// 노드의 끝까지 이동
while (node.next != null) {
node = node.next;
}
// 끝 노드의 다음 노드로 데이터를 가진 새로운 노드 생성
node.next = new Node<T>(data);
// 생성한 노드의 prev를 끝 노드로 지정
node.next.prev = node;
// 지금 생성한 노드를 tail로 지정
this.tail = node.next;
}
}
public void printAll() {
if(this.head != null) {
Node<T> node = this.head;
System.out.println(node.data);
// 노드의 끝까지 탐색
while(node.next != null) {
node = node.next;
System.out.println(node.data);
}
}
}
// head 부터 특정 노드를 찾는 메서드
public T searchFromHead(T isData) {
// 비어있으면 null 반환
if(this.head == null) {
return null;
} else {
Node<T> node = this.head;
// 노드 끝까지 데이터 일치하는 노드 탐색
while(node != null) {
if(node.data == isData) {
return node.data;
} else {
node = node.next;
}
}
// 못찾으면 null 반환
return null;
}
}
public T searchFromTail(T isData) {
// 비어있으면 null 반환
if(this.head == null) {
return null;
} else {
Node<T> node = this.tail;
// 노드 끝까지 데이터 일치하는 노드 탐색
while(node != null) {
if(node.data == isData) {
return node.data;
} else {
node = node.prev;
}
}
// 못찾으면 null 반환
return null;
}
}
// 추가
public boolean insertToFront(T existedData, T addData) {
// 비어 있으면 head에 데이터 추가
if (this.head == null) {
this.head = new Node<T>(addData);
this.tail = this.head;
return true;
}
// head가 찾는 데이터 값일 경우
else if (this.head.data == existedData) {
// 새로운 노드 newHead로 생성
Node<T> newHead = new Node<T>(addData);
// 새로운 노드의 다음 노드를 현재 헤드 노드로 설정
newHead.next = this.head;
// 헤드를 새로운 노드로 설정
this.head = newHead;
// 찾았으니까 true
return true;
} else {
// node에 헤드 담기
Node<T> node = this.head;
// 노드 끝까지 탐색
while (node != null) {
// 찾는 데이터 값을 찾으면
if (node.data == existedData) {
// 찾은 노드의 이전 노드를 변수 nodePrev로 설정
Node<T> nodePrev = node.prev;
// next 설정
nodePrev.next = new Node<T>(addData);
nodePrev.next.next = node;
// prev 설정
nodePrev.next.prev = nodePrev;
node.prev = nodePrev.next;
// 찾았으니까 true
return true;
} else {
node = node.next;
}
}
// 못찾았으니까 false
return false;
}
}
public static void main(String[] args) {
DLinkedList<Integer> list = new DLinkedList<>();
}
}
출처
'Algorithm > 자료구조' 카테고리의 다른 글
| [자료구조] Set Collection (0) | 2022.02.21 |
|---|---|
| [자료구조] 배열 (Array), 큐(Queue), 스택(Stack) (0) | 2022.02.15 |