1. Linked List (연결리스트)
연결리스트는 기존 배열리스트가 삽입, 삭제시 배열을 새로 만들고 옮겨담아야 한다는 문제를 해결하기 위해 등장하였다. 아래의 그림을 보면 연결리스트의 동작을 쉽게 이해할 수 있다.
연결리스트는 기본적으로 노드(Node)라는 구조체를 기본으로 한다. 연결리스트에서의 노드는 위의 그림처럼 데이터칸과 주소칸 두칸으로 이루어진 자료구조인데, 데이터칸에는 현재 인덱스의 데이터를 저장하고 있고, 주소칸는 다음 인덱스의 주소를 저장하고 있다. 이러한 구조 때문에 연결리스트는 다음과 같은 특징을 가지고 있다.
-
데이터의 이동 없이 중간에 삽입 / 삭제 가능함. 이는 연결리스트가 상수시간에 확장할 수 있게 해주는 가장 큰 요인임. 배열리스트의 경우 새로운 배열을 생성하거나 데이터를 이동하기 위한 시간이 소모되기 때문에 삽입/삭제의 경우 연결리스트가 훨씬 빠르다.
-
랜덤엑세스가 불가능함. 데이터를 연결된 주소에 저장하는 것이 아니라 따로 떨어뜨려서 저장하고 그들의 주소를 이어서 만든 구조이기 때문에 원하는 주소로 바로 접근하지 못하고 노드의 주소칸을 계속해서 타고 넘어야 원하는 원소의 주소에 도달할 수 있음. 빠른 삽입/삭제 능력을 얻었지만 곱하기와 더하기 연산만으로 매우 빠르게 탐색할 수 있는 배열리스트의 가장 큰 장점이 사라졌다.
-
Head의 주소는 반드시 기억해야한다. 때문에 메모리를 해제할 때에도 반드시 뒤에서부터 해제해야한다. 만약 Head의 주소를 잃어버리게 되면 뒤쪽 원소들을 탐색하거나 데이터를 삽입/삭제 하는 등의 연산을 수행할 수 없다.
2. Linked List의 연산
1) 삽입 연산 : 기존 배열리스트와 다르게 삽입시에는 새로운 노드 구조체를 만들고 원하는 위치보다 한칸 앞의 노드의 주소칸을 새로운 노드로 변경하고, 기존에 있던 주소값을 새로운 노드의 주소칸으로 옮긴다. 이러한 연산 때문에 삽입시에 배열리스트에 비해 매우 유연하게 연산을 수행할 수 있다. 아래 그림을 보면 삽입과정이 매우 쉽게 이해 될 것이다.
2) 삭제 연산 : 기존 배열리스트와 다르게 이전 원소들을 전부 옮겨 담을 필요 없이 삭제하기를 원하는 원소의 앞 원소와 뒤 원소를 이어주고, 원하는 원소(노드)를 메모리에서 해제해주면 된다. 배열리스트와 대비하여 삭제시에도 매우 유연하게 처리 가능하다.
3) 탐색 연산 : 데이터들이 모두 떨어져서 저장되어있기 때문에 더 이상 인덱스를 이용해 랜덤액세스를 할 수 없다. 때문에 n번째 원소를 찾으려면 n번의 루프를 돌아서 노드들의 주소를 타고 넘어야한다.
4. 연결리스트의 단점들
연결리스트는 매우 유연하게 삽입과 삭제를 수행할 수 있다는 장점이 있지만 단점 또한 매우 극명하다. 이 챕터에서는 연결리스트 가진 단점들에 대해서 알아본다.
1) 캐싱에 적합하지 않은 구조 : 연결리스트의 탐색은 loop를 돌아야 하기 때문에 O(n)의 시간복잡도를 갖고 배열리스트의 탐색은 상수시간에 계산이 가능하기 때문에 O(1)의 시간복잡도를 갖는다. 때문에 배열리스트의 탐색이 빠르다는 것이 자명하다. 그러나 실제로 시간을 계산해보면 이러한 차이 이상으로 배열리스트의 연산이 연결리스트에 비해 압도적으로 빠르다. 이유가 무엇일까?
정답은 컴퓨터 안에 있는 캐시(Cache)라는 저장 공간 때문이다. CPU는 메인메모리에 적재(load)된 소스코드를 한줄씩 읽어서 처리하는데 메인메모리(RAM)의 경우 프로세서(CPU)에 비해 데이터 처리 속도가 압도적으로 느리다. 때문에 CPU에서 작업을 완료해도 메인메모리에 있는 데이터나 소스코드가 전송되지 않아서 CPU가 오랜시간 대기하는 경우가 생긴다. 이러한 문제를 해결하기 위해 이 둘 사이에 캐시라는 저장공간을 만들고 메인메모리에 적재된 정보 중 일부를 캐시에 미리 적재한다. 캐시는 SRAM기반으로 DRAM기반의 메인메모리보다 훨씬 빠르다. CPU는 메인메모리가 아닌 캐시에서 정보들을 가져오게 되고 이러한 캐싱 방식을 이용하면 CPU가 쉬는 시간을 극도로 줄일 수 있다.
배열리스트의 경우 같은 타입의 데이터들이 연속된 메모리 공간에 저장되어있다. 때문에 메모리에서 캐시로 데이터를 넘길 때 이 데이터들이 한번에 같이 넘어가서 CPU가 매우 빨리 이들을 처리할 수 있는데, 연결리스트의 경우 데이터를 메모리 곳곳에 저장한 뒤 이들을 주소로만 연결해놓은 구조이기 때문에 데이터가 캐시로 한번에 넘어오지 못하고 CPU가 이들이 넘어올 때 까지 기다려야 하므로 처리속도가 매우 느려지게 된다.
2) 복잡한 연산에 따른 오버헤드 발생 : 일반적으로 배열리스트의 연산들보다 연결리스트의 연산들이 훨씬 복잡하다. 때문에 모든 연산을 수행할 때 더 많은 명령어가 필요하고 때문에 더 많은 오버헤드가 발생하게 된다. 이러한 이유로 알고리즘의 시간 복잡도 이외에도 추가적인 시간들이 소모된다.
3) 주소 저장으로 인한 공간 낭비 : 연결리스트의 경우 데이터 이외에도 주소에 대한 정보를 반드시 가지고 있어야하기 때문에 주소에 대한 용량이 소모된다. 일반적으로 정수형 리스트의 경우 데이터(integer), 주소(integer)를 저장하기 때문에 배열리스트와 비교하여 2배의 용량이 필요하다.
5. 개선된 연결리스트 구조
1) Doubly Linked List (이중 연결리스트) : 일반적으로 연결리스트라고 하더라도 앞쪽의 원소를 검색하면 속도면에서 배열리스트와 큰 차이가 나지 않는다. 그러나 뒷쪽의 원소를 검색하면 loop를 그 만큼 돌아야하기 때문에 탐색속도가 많이 느려지게 된다. 이러한 문제를 해결하기 위해 뒷쪽 원소들도 빠르게 검색할 수 있는 Doubly Linked List (이중 연결리스트) 구조가 있다.
이중 연결리스트 기존 단일 연결리스트와 다르게 2개의 주소칸을 갖는다. 추가된 주소칸은 다음 원소의 주소가 아닌 이전 원소의 주소를 기억하고 Head뿐만 아니라 가장 끝 원소인 Tail의 주소도 기억한다. 만약 사용자가 특정 인덱스의 탐색을 요청하면 해당 인덱스가 전체 리스트의 중앙보다 앞쪽인지 뒷쪽인지 판단하여 만약 앞쪽이라면 Head를 이용하여 탐색하고 뒷쪽이라면 Tail을 이용하여 탐색한다. 그러나 주소를 2개 저장해야해서 저장공간이 추가로 더 필요하다는 단점이 있다.
2) Circular Linked List (원형 연결리스트) : 연결리스트는 항상 앞에서만 탐색을 수행해야한다. 이중 연결리스트 구조를 적용한다고 해도 앞 혹은 뒤에서만 탐색을 수행할 수 있다. 그러나 개발자 입장에서 어떤 순간에는 작업하던 곳에서 이어서 탐색을 진행하고 싶을 수 있다. 이러한 문제를 해결하기 위해 앞과 뒤가 연결되어있고 마지막 작업한 위치를 Head이자 Tail로 설정된 Circular Linked List (원형 연결리스트) 구조가 있다.
원형리스트를 사용하면 굳이 Head가 어디인지, Tail이 어디인지 신경 쓸 필요가 없다. 때문에 마지막 작업하던 위치에서 이어서 탐색, 삽입, 삭제 등의 연산등을 곧 바로 수행할 수 있다는 장점이 있다. 그러나 데이터의 순서의 개념이 모호해지고, 때문에 인덱스를 이용한 탐색이 어렵다는 단점이 있다.
6. Case Study : Java
배열리스트와 마찬가지로 이번에도 JDK의 코드를 분석하며 실제 연결리스트가 어떻게 구현되어있는지 확인한다.
1) Node Structure : 연결리스트에서 가장 중요한 Node Structure이다. item외에도 next, prev 노드를 보유하고 있다. 다음 주소 이외에도 이전 주소를 보유하고 있기 때문에 JDK의 연결리스트는 이중 연결리스트 구조를 가지고 있다는 것을 알 수 있음.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2) 삽입 연산 : 원소를 중간에 삽입한다. 새로운 노드를 생성하고 이 노드를 앞 노드와 뒤 노드 사이에 연결시킨다.
/**
* 해당 인덱스로 원소 추가
* 기존 원소는 뒤로 밀림 (링크만 변경해주는 것으로 배열리스트와 다름)
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 요소를 마지막에 연결함
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
/**
* succ(input node) 전에 e를 연결함
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
3) 삭제 연산 : 해당 원소의 앞, 뒤 원소를 서로 연결시키고 현재 원소를 해제한다. 자바에서는 직접 free()를 호출할 필요는 없지만 gc시 System이 힙에서 더 잘 발견할 수 있도록 원소를 null로 만들어줌.
/**
* 해당 인덱스의 원소 제거
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* 노드 x를 언링크
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
4) 탐색 연산 : 원소를 탐색함. for loop를 통해 노드를 탐색하고 해당 노드의 item을 반환한다.
/**
* 해당 인덱스의 원소 리턴
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* 해당 노드의 원소 리턴
* */
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // 절반보다 앞에 있으면 헤드부터 검색
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 절반보다 뒤에 있으면 꼬리부터 검색
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
7. 구현
C로 직접 구현한 연결리스트 구현체이다. 모든 함수에 도큐먼테이션을 달아놓았으니 자세한 설명은 주석을 참고하면 된다.
1) 단일 연결리스트
/**
* Singly LinkedList Implementation
*
* @author : Hyunwoong
* @when : 7/30/2019 2:12 PM
* @homepage : https://github.com/gusdnd852
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedNode {
struct LinkedNode *next;
int data;
} LinkedNode;
typedef struct LinkedList {
LinkedNode *head;
int count;
} LinkedList;
/**
* create new empty list
*
* @return new empty list
*/
LinkedList *create() {
LinkedList *emptyList = (LinkedList *) malloc(sizeof(LinkedList));
emptyList->count = 0;
emptyList->head = NULL;
return emptyList;
}
/**
* return list's size
*
* @param list list to check size
* @return list's size
* */
int size(LinkedList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
return list->count;
}
/**
* check whether list is empty or not
*
* @param list list to check
* @return whether empty or not (0 : not empty , 1 : empty)
* */
int isEmpty(LinkedList* list){
if(list == NULL){
printf("NullPointerException Occurred\n");
exit(1);
}
return size(list) == 0 ? 1 : 0;
}
/**
* insert an element at list's front
*
* @param list list to insert
* @param elem element to insert
* */
void insertFirst(LinkedList *list, int elem) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if(list->head == NULL){
LinkedNode *newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
newNode->next = NULL;
newNode->data = elem;
list->head = newNode;
list->count++;
return;
}
LinkedNode *newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
LinkedNode *oldHead = list->head;
newNode->data = elem;
newNode->next = oldHead;
list->head = newNode;
list->count++;
}
/**
* insert an element at list's back
*
* @param list list to insert
* @param elem element to insert
* */
void insertLast(LinkedList *list, int elem) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if(list->head == NULL){
LinkedNode *newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
newNode->next = NULL;
newNode->data = elem;
list->head = newNode;
list->count++;
return;
}
LinkedNode *search = list->head;
while(search->next != NULL){
search = search->next;
}
LinkedNode *newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
newNode->data = elem;
newNode->next = NULL;
search->next = newNode;
list->count++;
}
/**
* insert an element at index that user request
*
* @param list list to insert
* @param elem element to insert
* @param index index that user request
* */
void insert(LinkedList *list, int elem, int index){
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
if(index == 0){
insertFirst(list, elem);
return;
}
if(index == list->count){
insertLast(list, elem);
return;
}
if(list->head == NULL){
LinkedNode *newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
newNode->next = NULL;
newNode->data = elem;
list->head = newNode;
list->count++;
return;
}
LinkedNode *search = list->head;
int i;
for(i = 0 ; i < index-1 ; i++){
search = search->next;
}
LinkedNode *newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
newNode->data = elem;
newNode->next = search->next;
search->next = newNode;
list->count++;
}
/**
* remove an element at list's front
*
* @param list list to remove
* */
void removeFirst(LinkedList* list){
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
LinkedNode *oldHead = list->head;
LinkedNode *newHead = oldHead->next;
list->head = newHead;
free(oldHead);
list->count--;
}
/**
* remove an element at list's back
*
* @param list list to remove
* */
void removeLast(LinkedList *list){
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
LinkedNode *newLast = list->head;
int i;
for(i = 0 ; i < list->count-2 ; i++){
newLast = newLast->next;
}
LinkedNode* oldLast = newLast->next;
newLast->next = NULL;
free(oldLast);
list->count--;
}
/**
* remove an element at index that user request
*
* @param list list to remove
* @param index index that user request
* */
void removeIndex(LinkedList *list, int index) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
if (index == 0) {
removeFirst(list);
return;
}
if (index == list->count) {
removeLast(list);
return;
}
LinkedNode *prev = list->head;
int i;
for (i = 0; i < index - 1; i++) {
prev = prev->next;
}
LinkedNode *remove = prev->next;
LinkedNode *next = prev->next->next;
prev->next = next;
free(remove);
list->count--;
}
/**
* return an element at index that user request
*
* @param list list to search
* @param index index that user request
* @return an element located index that user request
* */
int get(LinkedList *list, int index) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
LinkedNode *search = list->head;
int i;
for(i = 0 ; i < index ; i++){
search = search->next;
}
return search->data;
}
/**
* print list like below
* list = [1 , 2 , 3]
*
* @param list list to print
* */
void printList(LinkedList *list){
if(list == NULL){
printf("NullPointerException Occurred\n");
exit(1);
}
int count = size(list);
int i;
LinkedNode* search = list->head;
if(search == NULL){
printf("List is Empty");
return;;
}
printf("list = [");
for(i=0 ; i<count ; i++){
printf("%d", search->data);
search = search->next;
if(i != count-1){
printf(" , ");
}
}
printf("]\n");
}
/**
* return memory located wasted list
*
* @param list list to return
* */
void freeList(LinkedList *list){
if(list == NULL){
printf("NullPointerException Occurred");
exit(1);
}
LinkedNode *head = list->head;
while(head != NULL){
LinkedNode *remove = head;
head = head->next;
free(remove);
}
free(list);
}
int main() {
LinkedList *list = create();
insertLast(list, 1); // [1]
insertLast(list, 2); // [1, 2]
insertLast(list, 3); // [1, 2, 3]
insertFirst(list, 4); // [4, 1, 2, 3]
insertFirst(list, 5);; // [5, 4, 1, 2, 3]
insert(list, 6, 3);; // [5, 4, 1, 6, 2, 3]
insert(list, 7, 0);; // [7, 5, 4, 1, 6, 2, 3]
insert(list, 8, 7);; // [7, 5, 4, 1, 6, 2, 3, 8]
removeFirst(list); // [5, 4, 1, 6, 2, 3, 8]
removeFirst(list); // [4, 1, 6, 2, 3, 8]
removeLast(list); // [4, 1, 6, 2, 3]
removeLast(list); // [4, 1, 6, 2]
removeIndex(list, 2); // [4, 1, 2]
printList(list);
printf("list[0] = %d\n", get(list, 0)); // 4
printf("list[1] = %d\n", get(list, 1)); // 1
printf("list[2] = %d\n", get(list, 2)); // 2
printf("is list empty ? {0:NO, 1:YES) => %d\n", isEmpty(list)); // 0
printf("size = %d\n", size(list)); // 3
freeList(list);
return 0;
}
2) 이중 연결 리스트
/**
* @author : Hyunwoong
* @when : 7/30/2019 2:12 PM
* @homepage : https://github.com/gusdnd852
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedNode {
struct LinkedNode *next;
struct LinkedNode *prev;
int data;
} LinkedNode;
typedef struct LinkedList {
LinkedNode *head;
LinkedNode *tail;
int count;
} LinkedList;
/**
* create new empty list
*
* @return new empty list
*/
LinkedList *create() {
LinkedList *emptyList = (LinkedList *) malloc(sizeof(LinkedList));
emptyList->count = 0;
emptyList->head = NULL;
emptyList->tail = NULL;
return emptyList;
}
/**
* return list's size
*
* @param list list to check size
* @return list's size
* */
int size(LinkedList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
return list->count;
}
/**
* check whether list is empty or not
*
* @param list list to check
* @return whether empty or not (0 : not empty , 1 : empty)
* */
int isEmpty(LinkedList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
return size(list) == 0 ? 1 : 0;
}
/**
* insert an element at list's front
*
* @param list list to insert
* @param elem element to insert
* */
void insertFirst(LinkedList *list, int elem) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (list->head == NULL) {
LinkedNode *newNode = (LinkedNode *) malloc(sizeof(LinkedNode));
newNode->next = NULL;
newNode->prev = NULL;
newNode->data = elem;
list->head = newNode;
list->tail = newNode;
list->count++;
return;
}
LinkedNode *newNode = (LinkedNode *) malloc(sizeof(LinkedNode));
LinkedNode *oldHead = list->head;
newNode->data = elem;
newNode->next = oldHead;
newNode->prev = NULL;
oldHead->prev = newNode;
list->head = newNode;
list->count++;
}
/**
* insert an element at list's back
*
* @param list list to insert
* @param elem element to insert
* */
void insertLast(LinkedList *list, int elem) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (list->head == NULL) {
LinkedNode *newNode = (LinkedNode *) malloc(sizeof(LinkedNode));
newNode->next = NULL;
newNode->prev = NULL;
newNode->data = elem;
list->head = newNode;
list->tail = newNode;
list->count++;
return;
}
LinkedNode *oldNode = list->tail;
LinkedNode *newNode = (LinkedNode *) malloc(sizeof(LinkedNode));
newNode->data = elem;
newNode->next = NULL;
newNode->prev = oldNode;
oldNode->next = newNode;
list->tail = newNode;
list->count++;
}
/**
* insert an element at index that user request
*
* @param list list to insert
* @param elem element to insert
* @param index index that user request
* */
void insert(LinkedList *list, int elem, int index) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
if (index == 0) {
insertFirst(list, elem);
return;
}
if (index == list->count) {
insertLast(list, elem);
return;
}
if (index > list->count / 2) { // check whether head is more near or tail is more near
// case : tail is more near
LinkedNode *search = list->tail;
int i;
for (i = 0; i < index - 1; i++) {
search = search->prev;
}
LinkedNode *next = search->next;
LinkedNode *newNode = (LinkedNode *) malloc(sizeof(LinkedNode));
newNode->data = elem;
newNode->prev = search;
newNode->next = search->next;
search->next = newNode;
next->prev = newNode;
list->count++;
} else {
// case : head is more near
LinkedNode *search = list->head;
int i;
for (i = 0; i < index - 1; i++) {
search = search->next;
}
LinkedNode *next = search->next;
LinkedNode *newNode = (LinkedNode *) malloc(sizeof(LinkedNode));
newNode->data = elem;
newNode->prev = search;
newNode->next = search->next;
search->next = newNode;
next->prev = newNode;
list->count++;
}
}
/**
* remove an element at list's front
*
* @param list list to remove
* */
void removeFirst(LinkedList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
LinkedNode *oldHead = list->head;
LinkedNode *newHead = oldHead->next;
newHead->prev = NULL;
list->head = newHead;
free(oldHead);
list->count--;
}
/**
* remove an element at list's back
*
* @param list list to remove
* */
void removeLast(LinkedList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
LinkedNode *oldLast = list->tail;
LinkedNode *newLast = oldLast->prev;
newLast->next = NULL;
list->tail = newLast;
free(oldLast);
list->count--;
}
/**
* remove an element at index that user request
*
* @param list list to remove
* @param index index that user request
* */
void removeIndex(LinkedList *list, int index) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
if (index == 0) {
removeFirst(list);
return;
}
if (index == list->count) {
removeLast(list);
return;
}
if (index > list->count / 2) { // check whether head is more near or tail is more near
LinkedNode *prev = list->tail;
int i;
for (i = 0; i < index - 1; i++) {
prev = prev->prev;
}
LinkedNode *remove = prev->next;
LinkedNode *next = remove->next;
prev->next = next;
next->prev = prev;
free(remove);
list->count--;
} else {
LinkedNode *prev = list->head;
int i;
for (i = 0; i < index - 1; i++) {
prev = prev->next;
}
LinkedNode *remove = prev->next;
LinkedNode *next = remove->next;
prev->next = next;
next->prev = prev;
free(remove);
list->count--;
}
}
/**
* return an element at index that user request
*
* @param list list to search
* @param index index that user request
* @return an element located index that user request
* */
int get(LinkedList *list, int index) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
if (index > list->count / 2) {
LinkedNode *search = list->tail;
int i;
for (i = 0; i < list->count - index - 1; i++) {
search = search->prev;
}
return search->data;
} else {
LinkedNode *search = list->head;
int i;
for (i = 0; i < index; i++) {
search = search->next;
}
return search->data;
}
}
/**
* print list like below
* list = [1 , 2 , 3]
*
* @param list list to print
* */
void printList(LinkedList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
int count = size(list);
int i;
LinkedNode *search = list->head;
if (search == NULL) {
printf("List is Empty");
return;;
}
printf("list = [");
for (i = 0; i < count; i++) {
printf("%d", search->data);
search = search->next;
if (i != count - 1) {
printf(" , ");
}
}
printf("]\n");
}
/**
* print list like below
* reverse = [1 , 2 , 3]
*
* @param list list to print
* */
void printReverse(LinkedList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
int count = size(list);
int i;
LinkedNode *search = list->tail;
if (search == NULL) {
printf("List is Empty");
return;;
}
printf("reverse = [");
for (i = 0; i < count; i++) {
printf("%d", search->data);
search = search->prev;
if (i != count - 1) {
printf(" , ");
}
}
printf("]\n");
}
/**
* return memory located wasted list
*
* @param list list to return
* */
void freeList(LinkedList *list) {
if (list == NULL) {
printf("NullPointerException Occurred");
exit(1);
}
LinkedNode *head = list->head;
while (head != NULL) {
LinkedNode *remove = head;
head = head->next;
free(remove);
}
free(list);
}
int main() {
LinkedList *list = create();
insertLast(list, 1); // [1]
insertLast(list, 2); // [1, 2]
insertFirst(list, 3); // [3, 1, 2]
insertFirst(list, 4); // [4, 3, 1, 2]
insert(list, 5, 1); // [4, 5, 3, 1, 2]
insert(list, 6, 3); // [4, 5, 3, 6, 1, 2]
removeFirst(list); // [5, 3, 6, 1, 2]
removeLast(list); // [5, 3, 6, 1]
removeIndex(list, 1); // [5, 6, 1]
insertFirst(list, 3); // [3, 5, 6, 1]
insertFirst(list, 4); // [4, 3, 5, 6, 1]
removeIndex(list, 3); // [4, 3, 5, 1]
insertFirst(list, 2); // [2, 4, 3, 5, 1]
printList(list);
printReverse(list);
printf("list[0] = %d\n", get(list, 0)); // 2
printf("list[1] = %d\n", get(list, 1)); // 4
printf("list[3] = %d\n", get(list, 3)); // 5
printf("is list empty ? {0:NO, 1:YES) => %d\n", isEmpty(list)); // 0
printf("size = %d\n", size(list)); // 5
printList(list);
freeList(list);
return 0;
}
모든 소스코드는 Github에서 확인할 수 있습니다.
github.com
'알고리즘' 카테고리의 다른 글
| 큐 (1) - 선형 큐 (0) | 2020.04.30 |
|---|---|
| 스택 (2) - 후위 표기법 계산기 (0) | 2020.04.30 |
| 스택 (1) - 개요 (0) | 2020.04.30 |
| 리스트 (2) - 배열 리스트 (Array List) (0) | 2020.04.28 |
| 리스트 (1) - 개요 (0) | 2020.04.28 |
| 문자열 알고리즘 (5) - 트라이 (Trie) (0) | 2020.03.05 |
| 문자열 알고리즘 (4) - 최장 공통부분 문자열 (Longest Common String) (0) | 2020.03.05 |