반응형
연결 리스트
- 연결 리스트란 각 노드가 데이터와 참조값을 갖고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조라 한다.
head: head는 연결 리스트의 시작으로 첫 번째 노드를 가리키는 노드를 의미 한다.
Node : 데이터와 다음 노드로 접근할 수 있는 참조값을 가지고 있다.
Pointer : 노드의 참조 값을 가리키는 변수를 의미한다.
Array vs LinkedList
- 조회가 많은 경우 Array를 사용, 삽입 또는 삭제가 많은 경우 LinkedList를 사용하는 것이 적합하다.
단일 연결 리스트
장점 : 저장 될 데이터 수를 몰라도 사용할 수 있다. 또한 사용한 만큼 메모리 공간을 할당하기 때문에 효율적인 메모리 관리를 할 수 있다.
단점 : 하나의 연결만을 가지고 있기 때문에 순차적으로 탐색해야 한다. 즉, 탐색 속도가 O(N)으로 느리며, 노드 간 연결이 잘못되었을 경우 원하는 노드를 찾지 못할 수 있다는 제약 조건이 있다.
단일 연결 리스트 삽입 및 삭제
노드 삽입, 삭제 시 맨 앞, 중간에 삽입하는 경우를 고려해야 한다.
맨 앞에 노드를 삽입할 때
- head에 포인터를 가리킨 후, 새로운 노드(New)를 생성한다. 새로운 노드(New)의 참조 값을 과거의 첫번째 노드(A)의 데이터를 가리키게 한다.
- Head에 새로운 노드의 참조값을 저장한다.
중간에 노드를 삽입할 때
- 삽입할 노드의 이전 노드에 포인터(A)를 가리킨 후, 새로운 노드(New)를 생성한다.
- 생성한 노드의 참조값을 포인터(A)가 가리킨 다음 노드(C)에 넣는다.
- 현재 포인터(A)에서 새로운 노드(New)의 참조값을 갖는다.
맨 앞에 노드를 삭제할 때
- 포인터는 head를 가리킨 후, A(삭제할 노드)가 가리키던 B의 참조값을 알아내서 head에 저장한다.
중간 노드를 삭제할 때
- 삭제할 노드(B)의 이전 노드(A)를 가리킨다. 이후 삭제할 노드가 가리키던 다음 노드(C)의 참조 값을 가져와서 포인터가 가리키는 노드의 참조값에 넣는다.
단일 연결 리스트 구현
- 다음과 같이 단일 연결리스트를 자바로 구현해보자.
SimpleLinkedList
package ds;
public class SimpleLinkedList <T> {
Node<T> head;
int size = 0;
private Node<T> findNode(int searchIdx) {
if(searchIdx < 0 || searchIdx >= size) throw new ArrayIndexOutOfBoundsException();
int idx = 0;
Node<T> pointer = head;
while (idx != searchIdx) {
idx++;
pointer = pointer.next;
}
return pointer;
}
public T getData(int searchIdx) {
return findNode(searchIdx).data;
}
public boolean isEmpty() {
return size == 0;
}
public void addLast(T data) {
add(size, data);
}
public void addFirst(T data) {
add(0, data);
}
public void removeLast() {
remove(size - 1);
}
public void removeFirst() {
remove(0);
}
public void remove(int idx) {
if(idx == 0 && head != null) {
head = head.next;
} else {
Node<T> prevNode = findNode(idx - 1);
prevNode.next = prevNode.next.next;
}
--size;
}
public void add(int idx, T data) {
Node<T> node = new Node<>();
node.data = data;
if (idx == 0) {
node.next = head;
head = node;
} else {
Node<T> foundNode = findNode(idx - 1);
node.next = foundNode.next;
foundNode.next = node;
}
++size;
}
static class Node<E> {
Node<E> next;
E data;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<T> pointer = head;
sb.append("head").append(" - ");
while (pointer != null) {
sb.append(pointer.data).append(" - ");
pointer = pointer.next;
}
sb.append("null");
return sb.toString();
}
}- Generic을 사용하여, 타입이 다를 경우의 오류를 컴파일 시점에서 잡을 수 있도록 구현하자.
SimpleMain
package ds;
public class SimpleMain {
static StringBuilder sb = new StringBuilder();
static SimpleLinkedList<String> list;
public static void main(String[] args) {
list = new SimpleLinkedList<>();
list.addLast("a");
append();
list.addLast("b");
append();
list.addFirst("C");
append();
list.remove(1);
append();
list.removeFirst();
append();
System.out.println(sb);
}
private static void append() {
sb.append(list).append("\n");
}
}이중 연결 리스트
- 이중 연결 리스트는 단일 연결 리스트와 다르게 마지막 노드를 가리키는 tail이 추가적으로 존재한다. 노드 간 양쪽으로 연결이 되어있기 때문에 노드에서 좌/우측으로 접근할 수 있다.
- 단일 연결리스트와 마찬가지로 접근 및 검색은 O(N), 삽입 및 삭제는 O(1)의 시간복잡도를 갖는다.
이중 연결 리스트의 장점
단일 연결 리스트와 동일하게 데이터의 크기가 예측 불가능할 때 사용할 수 있으며, 필요한 만큼 메모리 공간을 사용하기 때문에 메모리를 절약할 수 있다. 단일 연결 리스트와 다르게 양방향 연결을 지향하기 때문에 뒤 쪽에 가까운 노드에 접근 시 tail을 이용하여 빠르게 접근할 수 있다.
이중 연결 리스트의 단점
단일 연결 리스트보다 구현이 복잡하며, 노드의 참조값을 저장하는 변수가 하나 추가됨으로 더 많은 메모리 공간을 사용하게 된다.
이중 연결 리스트 삽입
최초로 노드를 삽입할 때
- 최초로 노드를 삽일 할 때 head와 tail은 null인 상태이며 노드를 생성한 후 head와 tail에 새로운 노드의 참조값을 저장한다.
맨 앞에 노드를 삽입할 때
맨 뒤에 노드를 삽입할 때
중간에 노드를 삽입할 때
이중 연결 리스트 삭제
노드가 한 개일 때 삭제
맨 앞의 노드를 삭제할 때
맨 뒤의 노드를 삭제할 때
중간의 노드를 삭제할 때
이중 연결 리스트 구현
package ds;
public class DoubleLinkedList {
Node head = null;
Node tail = null;
int size = 0;
private Node findNode(int searchIndex) {
if (0 > searchIndex || size <= searchIndex) {
throw new ArrayIndexOutOfBoundsException();
}
int nodeIndex;
Node pointer;
// index가 왼쪽에 가까우므로 head부터 탐색 .
if (size / 2 > searchIndex) {
nodeIndex = 0;
pointer = head;
while (nodeIndex != searchIndex) {
++nodeIndex;
pointer = pointer.right;
}
} else {
nodeIndex = size -1;
pointer = tail;
while (nodeIndex != searchIndex) {
--nodeIndex;
pointer = pointer.left;
}
}
return pointer;
}
public Object getData(int searchIndex) {
return findNode(searchIndex).data;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void addLast(Object data) {
add(size, data);
}
public void addFirest(Object data) {
add(0, data);
}
public void removeFirst() {
remove(0);
}
public void add(int index, Object data) {
Node node = new Node();
node.data = data;
if (index == 0 || index == size) {
// 최초 노드 삽입일 때
if (this.head == null && this.tail == null) {
this.head = node;
this.tail = node;
} else if (index == 0) {
// 맨 앞에 노드를 삽입할 때
node.right = this.head;
this.head.right = node;
this.head = node;
} else {
// 맨 뒤에 노드를 삽입
node.left = this.tail;
this.tail.right = node;
this.tail = node;
}
} else {
Node findNode = findNode(index);
Node leftNode = findNode.left;
node.right = findNode;
findNode.left = node;
node.left = leftNode;
leftNode.right = node;
}
++size;
}
public void remove(int index) {
Node removeNode = findNode(index);
Node leftNode = removeNode.left;
Node rightNode = removeNode.right;
if (leftNode != null) {
leftNode.right = rightNode;
}
if (rightNode != null) {
rightNode.left = leftNode;
}
if (index == 0) {
this.head = rightNode;
}
if (size - 1 == index) {
this.tail = leftNode;
}
removeNode.left = null;
removeNode.right = null;
removeNode.data = null;
--size;
}
static class Node {
Node left;
Node right;
Object data;
}
}REFERENCES
반응형
