바킹독 님의 유튜브 영상과 블로그 자료를 보고 정리한 내용입니다.
글 마지막에 출처 참고해주세요.
정의와 성질
- 정의
연결 리스트는 원소를 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조이다.
- 성질
연결리스트에서는 k번째 원소를 찾기 위해 O(k)가 필요하다. 이는 배열과 다르게 공간에 원소들이 연속해서 위치하지 않고 있기 때문이다. 또한 임의의 위치에 원소를 추가하거나 임의 위치의 원소 제거가 O(1)이다. 이는 배열과의 큰 차이면서 연결리스트의 장점이다. 또한 메모리 상 데이터가 연속적이지 않아 Cache hit rate가 낮지만 할당이 쉽다.
- 종류
- 단일 연결 리스트 : 각 원소가 자신의 다음 원소의 주소를 갖고 있다.
- 이중 연결 리스트 : 각 원소가 자신의 이전 원소와 다음 원소의 주소를 갖고 있다.
다만 원소가 갖고 있어야 하는 정보가 1개 더 추가되어 메모리 사용량이 증가한다.
- 원형 연결 리스트 : 끝이 처음과 연결되어 있다. 각 원소가 이전과 다음 원소의 주소를 모두 보유하고 있어도 상관없다.
배열과 연결리스트
메모리 상에 원소를 놓는 방법이 다르지만 원소들 사이의 선후 관계가 일대일로 정의되는 선형 구조라는 공통점이 있다.
배열에 익숙하다 보니 연결 리스트 자료구조를 어디에 사용하나 싶은 생각이 많이 들게 되는데, 연결 리스트는 메모장과 같은 텍스트 에디터에서 주로 사용한다. 단순하게 메모를 입력하고 출력하는 메모장을 생각하면 배열로 구현하는 경우가 많지만, 만약 커서가 가르키는 위치에 계속해서 문자를 추가하거나 삭제해야하는 수행을 원한다면 연결 리스트로 구현하는 것이 효율적이다. 즉, 임의의 위치 원소를 추가 / 제거하는 연산을 많이 하는 경우에 연결 리스트의 사용을 고려하면 된다.
cf. 비선형구조 - 트리, 그래프, 해쉬 등
| 배열 | 연결 리스트 | |
| k번째 원소의 접근 | O(1) | O(k) |
| 임의 위치에 원소 추가 / 제거 | O(N) | O(1) |
| 메모리 상의 배치 | 연속 | 불연속 |
| 추가적으로 필요한 공간 (Overhead) | - | O(N) |
-> 임의 위치에 원소를 추가하는 부분에서 정확하게 보자면 연결 리스트에서도 원소를 추가하고자 하는 위치 앞단계까지는 찾아간 이후에 추가가 가능하다. (구현 파트에서 추가 설명)
-> 추가적으로 필요한 공간인 overhead에서 배열은 데이터만 저장하면 될 뿐 추가적으로 필요한 공간이 없다. 쪼~금이라도 있다면 길이 정보를 저장할 int 1개가 정도이지만 신경 쓸 필요가 없다. 그러나 연결 리스트에서는 각 원소가 다음 원소 , 혹은 이전과 다음 원소의 주소 값을 가지고 있어햐 하기 때문에 32bit 컴퓨터면 주소값이 32bit단위이니 4N byte가 추가로 필요하고 64bit 컴퓨터라면 주소값이 64bit 단위이니 8N byte가 추가로 필요해진다. 즉, N에 비례하는 만큼 메모리가 추가로 필요하다.
기능과 구현
- 임의의 위치에 있는 원소 확인 / 변경
처음에는 첫 번째 원소의 주소만 알고 있기 때문에 k번째 원소를 확인하기 위해서 첫 번째에 기록된 주소를 보고 두 번째 원소로 넘어가고, 두 번째에 기록된 주소를 보고 세 번째 원소를 넘어가고.. 를 반복하여 k번째 원소에 도착한다. 때문에 k번째 원소를 보기 위해서는 O(k)의 시간이 필요하고 전체에 N개의 원소가 있다고 하면 평균적으로 N/2의 시간이 걸릴테니 O(N)이라고 생각하면 된다.
- 임의의 위치에 원소 추가
k번째 임의의 위치에 원소를 추가하는데 만약 추가하고 싶은 위치의 주소를 알고 있다면 그 원소에 접근하여 다음으로 연결하는 주소를 추가하는 원소의 주소로 바꾸고 추가한 원소의 다음 주소에 원래 추가하고 싶은 위치 이후의 원소 주소값을 넣으면 된다. 때문에 그 시간은 O(1)만큼 걸린다. 하지만 만약 추가하고 싶은 위치만 알고 그 주소를 모른다면 O(1)이 걸린다고 할 수 없다.
- 임의의 위치의 원소 제거
지우고 싶은 원소 앞의 원소에서 보유한 다음 주소값을 제거하려고 하는 원소의 다음 원소의 주소값으로 고쳐주면 끝이다 때문에 O(1)만큼의 시간이 걸린다. 이때, 메모리 누수를 막기 위해 메모리를 없애야 한다.
구현 (Doubly Linkedlist)
더보기
public class MyDoublyLinkedList<E> {
private Node<E> head; // 노드의 첫 부분을 가리키는 레퍼런스
private Node<E> tail; // 노드의 끝 부분을 가리키는 레퍼런스
private int size; // 리스트 요소 갯수
// 생성자
public MyDoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// inner static class
private static class Node<E> {
private E item; // Node에 담을 데이터
private Node<E> next; // 다음 Node 객체를 가르키는 래퍼런스
private Node<E> prev; // 이전 Node 객체를 가르키는 래퍼런스
// 생성자 (이전 노드 포인트 | 데이터 | 다음 노드 포인트)
Node(Node<E> prev, E item, Node<E> next) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
private Node<E> search(int index) {
Node<E> n; // 반환할 노드
if ((size / 2) > index) {
// 1. 만일 인덱스가 시작에 가까우면, 순차 탐색
n = head;
for (int i = 0; i < index; i++) {
n = n.next;
}
} else {
// 2. 만일 인덱스가 끝에 가까우면, 역순 탐색
n = tail;
for (int i = size - 1; i > index; i--) {
n = n.prev;
}
}
return n;
}
public void addFirst(E value) {
// 1. head를 임시 백업함
Node<E> first = head;
// 2. 새 노드를 추가 (이때 첫번째 노드니까 prev는 null이 되고 next는 head가 가리키는 노드가 되게 된다)
Node<E> new_node = new Node<>(null, value, first);
// 3. 노드를 추가하였으니 리스트 크기 증가
size++;
// 4. 첫번째 기준이 변경되었으니 head를 삽입된 새 노드로 참조하도록 업데이트
head = new_node;
if (first == null) {
// 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우, tail도 첫째 노드를 바라보도록 업데이트
tail = new_node;
} else {
// 6. 만일 빈 리스트가 아닐경우, 추가되기 이전 첫번째이었던 노드에서 prev를 새 노드로 참조하도록 업데이트
first.prev = new_node;
}
}
public void addLast(E value) {
// 1. tail를 임시 백업함
Node<E> last = tail;
// 2. 새 노드를 추가 (이때 마지막 노드니까 next는 null이 되고 prev는 tail이 가리키는 노드가 되게 된다)
Node<E> new_node = new Node<>(last, value, null);
// 3. 노드를 추가하였으니 리스트 크기 증가
size++;
// 4. 마지막 기준이 변경되었으니 tail를 삽입된 새 노드로 참조하도록 업데이트
tail = new_node;
if (last == null) {
// 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우, head도 첫째 노드를 바라보도록 업데이트
head = new_node;
} else {
// 6. 만일 빈 리스트가 아닐경우, 추가되기 이전 마지막이었던 노드에서 next를 새 노드로 참조하도록 업데이트
last.next = new_node;
}
}
public boolean add(E value) {
addLast(value);
return true;
}
public void add(int index, E value) {
// 1. 인덱스 범위 체크
// 인덱스가 0보다 작거나 size 보다 클 경우 에러
// (인덱스가 size보다 크면 마지막 요소 다음 빈공간의 다음 빈공간을 가리키는 거니까)
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// 2. 추가하려는 index가 0이면 addFirst 호출
if (index == 0) {
addFirst(value);
return;
}
// 3. 추가하려는 index가 size와 같으면 addLast 호출
if (index == size) {
addLast(value);
return;
}
// 4. 추가하려는 위치의 다음 노드 얻기
Node<E> next_node = search(index);
// 5. 추가하려는 위치의 이전 노드 얻기
Node<E> prev_node = next_node.prev;
// 6. 새 노드 생성 (바로 이전 / 다음 노드와 연결됨)
Node<E> new_node = new Node<>(prev_node, value, next_node);
// 7. 노드를 추가하였으니 리스트 크기 증가
size++;
// 8. 이전 노드의 next를 새 노드에 연결
prev_node.next = new_node;
// 9. 다음 노드의 prev를 새 노드에 연결
next_node.prev = new_node;
}
public E removeFirst() {
// 1. 만약 삭제할 요소가 아무것도 없으면 에러
if (head == null) {
throw new NoSuchElementException();
}
// 2. 삭제될 첫번째 요소의 데이터를 백업
E value = head.item;
// 3. 두번째 노드를 임시 저장
Node<E> first = head.next;
// 4. 첫번째 노드의 내부 요소를 모두 삭제
head.next = null;
head.item = null;
// 5. 요소가 삭제 되었으니 크기 감소
size--;
// 6. head가 다음 노드를 가리키도록 업데이트
head = first;
if (first == null) {
// 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, tail도 null 처리
tail = null;
} else {
// 8. 만일 빈 리스트가 아닐경우, 삭제되기 이전 두번째 이었던 first가 첫번째 노드가 되니 prev를 null 처리
first.prev = null;
}
// 9. 마지막으로 삭제된 요소를 반환
return value;
}
public E remove() {
return removeFirst();
}
public E removeLast() {
// 1. 만약 삭제할 요소가 아무것도 없으면 에러
if (tail == null) {
throw new NoSuchElementException();
}
// 2. 삭제될 첫번째 요소의 데이터를 백업
E value = tail.item;
// 3. 마지막 노드의 이전 노드를 임시 저장
Node<E> last = tail.prev;
// 4. 마지막 노드의 내부 요소를 모두 삭제
tail.item = null;
tail.prev = null;
// 5. 요소가 삭제 되었으니 크기 감소
size--;
// 6. tail이 이전 노드를 가리키도록 업데이트
tail = last;
if (last == null) {
// 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, head도 null 처리
head = null;
} else {
// 8. 만일 빈 리스트가 아닐경우, 삭제되기 이전 마지막의 이전 노드 이었던 last가 마지막 노드가 되니 next를 null 처리
last.next = null;
}
// 9. 마지막으로 삭제된 요소를 반환
return value;
}
public E remove(int index) {
// 1. 인덱스가 0보다 작거나 size 보다 크거나 같은 경우 에러 (size와 같을 경우 빈 공간을 가리키는 거니까)
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. 인덱스가 0이면 removeFirst 메서드 실행
if (index == 0) {
return removeFirst();
}
// 3. 인덱스가 size - 1(마지막 요소 위치) 이면 removeLast 메서드 실행
if (index == size - 1) {
return removeLast();
}
// 4. 삭제할 위치의 노드 저장
Node<E> del_node = search(index);
// 5. 삭제할 위치의 이전 노드 저장
Node<E> prev_node = del_node.prev;
// 6. 삭제할 위치의 다음 노드 저장
Node<E> next_node = del_node.next;
// 7. 삭제될 첫번째 요소의 데이터를 백업
E value = del_node.item;
// 8. 삭제 노드의 내부 요소를 모두 삭제
del_node.item = null;
del_node.prev = null;
del_node.next = null;
// 9. 요소가 삭제 되었으니 크기 감소
size--;
// 10. 이전 노드가 다음 노드를 가리키도록 업데이트
prev_node.next = next_node;
// 11. 다음 노드가 이전 노드를 가리키도록 업데이트
next_node.prev = prev_node;
// 12. 마지막으로 삭제된 요소를 반환
return value;
}
public boolean remove(Object value) {
// 1. 삭제 노드를 저장할 변수 선언
Node<E> del_node = null;
// 2. 리스트를 루프할 변수 선언
Node<E> i = head;
// 3. 노드의 next를 순회하면서 해당 값을 찾는다.
while (i != null) {
// 노드의 값과 매개변수 값이 같으면
if (Objects.equals(i.item, value)) {
del_node = i; // 삭제 노드에 요소를 대입하고 break
break;
}
i = i.next;
}
// 4. 만일 찾은 요소가 없다면 false 리턴
if (del_node == null) {
return false;
}
// 5. 만약 삭제하려는 노드가 head(첫번째 요소) 라면, 기존 removeFirst()를 사용
if (del_node == head) {
removeFirst();
return true;
}
// 6. 만약 삭제하려는 노드가 last(마지막 요소) 라면, 기존 removeLast()를 사용
if (del_node == tail) {
removeLast();
return true;
}
// 7. 이전 노드, 다음 노드 구하기
Node<E> prev_node = del_node.prev;
Node<E> next_node = del_node.next;
// 8. 삭제 요소 데이터 모두 제거
del_node.item = null;
del_node.prev = null;
del_node.next = null;
// 9. 요소가 삭제 되었으니 크기 감소
size--;
// 10. 이전 노드와 다음 노드 끼리 서로 링크드 설정
prev_node.next = next_node;
next_node.prev = prev_node;
return true;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return search(index).item;
}
public void set(int index, E value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 1. search 메소드를 이용해 교체할 노드를 얻는다.
Node<E> replace_node = search(index);
// 2. 교체할 노드의 요소를 변경한다.
replace_node.item = null;
replace_node.item = value;
}
public int indexOf(Object value) {
Node<E> n = head;
int i = 0;
while (n != null) {
if (Objects.equals(value, n.item)) {
return i;
}
i++;
n = n.next;
}
return -1;
}
public int lastIndexOf(Object value) {
Node<E> n = tail;
int i = size - 1;
while (n != null) {
if (Objects.equals(value, n.item)) {
return i;
}
i--;
n = n.prev;
}
return -1;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
// i.next가 null이 면 마지막을 의미하는거니, null 이 아닐때 까지 순회
for (Node<E> i = head; i.next != null; ) {
Node<E> next_node = i.next; // i에 관한 모든 값을 지울 것이기 때문에 미리 백업한다.
i.item = null;
i.prev = null;
i.next = null;
i = next_node;
}
head = null;
tail = null;
size = 0; // 모든 요소를 지웠으니 size도 초기화
}
public boolean contains(Object value) {
return indexOf(value) != -1; // -1 이 아니라는 말은 요소가 리스트에 존재한다는 것이다.
}
@Override
public String toString() {
if (head == null) {
return "[]";
}
Node<E> n = head;
String result = "[";
while (n.next != null) {
result += n.item + ", ";
n = n.next;
}
// n이 마지막일 경우 n.next가 null이니 루프문을 빠져나오게 되서 마지막 노드 삽입 처리를 해주어야 한다.
result += n.item + "]";
return result;
}
public String toString2() {
if (head == null) {
return "[]";
}
Node<E> n = head;
StringBuilder result = new StringBuilder();
result.append("[\n");
for (int i = 0; i < size; i++) {
result.append(" Node@").append(String.format("%-10s", n.hashCode())).append(" → ");
if (n.prev != null) {
result.append("[").append(n.prev.hashCode()).append(" | ");
} else {
result.append("[").append("null").append(" | ");
}
result.append(n.item).append(" | ");
if (n.next != null) {
result.append(n.next.hashCode()).append("]");
} else {
result.append("null").append("]");
}
result.append(", \n");
n = n.next;
}
result.append("]");
return result.toString();
}
}
연습문제
에디터
더보기
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String text = reader.readLine();
Stack<String> stk = new Stack<>();
int cursor = text.length();
int num = Integer.parseInt(reader.readLine());
for (int i = 0; i < text.length(); i++) {
stk.push(String.valueOf(text.charAt(i)));
}
for (int j = 0; j < num; j++) {
String[] input = reader.readLine().split(" ");
int len = input.length;
switch (input[0]) {
case "L" :
if (cursor != 0) cursor--;
break;
case "D" :
if (cursor <= len) cursor++;
break;
case "B" :
if (cursor != 0) stk.remove(--cursor);
break;
case "P" :
stk.add(cursor, input[1]);
cursor++;
break;
}
}
for (int k = 0; k < stk.size(); k++) {
System.out.print(stk.elementAt(k));
}
}
* https://blog.encrypted.gg/932
'Algorithm' 카테고리의 다른 글
| [Algorithm] 프로그래머스 - 이중우선순위큐 (0) | 2024.04.23 |
|---|---|
| [Algorithm] 프로그래머스 고득점 kit - 전화번호 목록 (0) | 2024.03.17 |
| [Algorithm] 프로그래머스 정렬 - 가장 큰 수 (0) | 2024.03.10 |
| [Algorithm] 프로그래머스 정렬 - HIndex (0) | 2024.03.10 |
| [Algorithm] 정렬 (0) | 2024.03.04 |
