DS #2. 연결 리스트 (LinkedList)

두 번째로 자료구조에서 살펴 볼 내용은 연결 리스트(LinkedList)이다. 

 

연결 리스트

연결 리스트는 어떤 데이터 덩어리(이를 노드라고 표현)를 저장할 때, 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 자료구조이다. 따라서 각각의 노드들은 자기 자신 다음에 어떤 노드가 오는지를 기억하고 있다. 배열이 가지고 있는 단점들을 해결하기 위해서 만든 자료구조이다. 예를 들면 배열에서는 하나의 값을 삭제하고 추가하는 데에 시간복잡도가 O(n)이었다면, 연결 리스트에서는 삭제시에 하나의 노드를 빼 주고 나서 삭제된 노드 이전의 노드가 삭제된 노드 이후의 노드를 바로 참조할 수 있게 연결해 주면 되기 때문에 시간복잡도가 O(1)이고 삽입도 비슷한 이유로 O(1)이다.

연결리스트가 배열에 비해서 가지는 큰 장점은 이와 같이 삽입, 삭제가 빠르다는 점 이외에도 메모리 공간 측면에서도 유리하다. 배열은 크기를 크게 키우기가 어려운 단점이 있는데, 그 이유는 크기가 커지면 그만큼 '연속된' 공간을 할당하기가 어려워 지기 때문이다. 반면에 연결 리스트는 필요 시에만 메모리를 동적 할당하기 때문에 메모리 누수가 발생하지 않고 유연하게 공간을 관리할 수 있다는 장점이 있다. 

출처 : geeksforgeeks

연결 리스트에서의 삽입 (출처 : geeksforgeeks)

연결 리스트에도 단점이 존재하는데, 그것은 바로 탐색을 하는 데에 시간이 오래 걸린다는 점이다. 연결 리스트는 배열과 다르게 논리적 저장순서와 물리적 저장 순서가 일치하지 않는다. 배열의 경우 인덱스 값을 알면 O(1)로 탐색을 할 수 있었지만, 연결 리스트는 처음부터 하나씩 노드들은 확인해 가면서 탐색을 진행하기 때문에 탐색의 search의 시간 복잡도가 O(n)이다. 배열과 자주 비교되는 자료구조인데, 탐색 또는 정렬을 많이 하는 경우는 배열을 사용하는 것이 유리하고, 삽입/삭제를 많이 하는 자료구조라면 연결 리스트를 사용하는 것이 유리하다고 볼 수 있다. 여기서 배열과 연결 리스트의 장점을 합쳐서 데이터의 삽입/삭제/정렬/탐색이 모두 빠른 자료구조가 B-tree인데 이는 나중에 살펴보도록 하자.

지금부터는 리스트의 대표적인 유형들인 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트에 대해서 알아보자.

 

---

 

단순 연결 리스트

출처 : https://hyeonstorage.tistory.com/259

단순 연결 리스트(Singly linked list)는 다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트이다. 단순하지만 여러가지 약점을 가지고 있는데 예를 들면, 마지막 원소를 찾기 위해서 리스트 끝까지 탐색을 해야 한다.(O(n)) 그리고 Head 노드를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점도 가지고 있다. 또한 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에도 체인이 끊어진 뒤쪽 자료들을 유실한다. 이러한 이유로 안정적이지는 않다. 파일 시스템 중에서 FAT 파일 시스템이 이 단순 연결 리스트로 파일 청크를 연결하는데, 언급한 이유로 파일 내용 일부가 손상될 경우 파일의 상당 부분을 유실할 수 있고 랜덤 액세스 성능도 낮다.

Java로 구현한 단순 연결 리스트 코드는 다음과 같다.

public class MyLinkedList {
    
    private Node header;
    private int size;
    
    public MyLinkedList(){
        
        header = new Node(null);
        size = 0;
    }
    
    // 단순 연결 리스트 노드
    private class Node{
        
        private Object data;
        private Node nextNode;
        
        Node(Object data){
            
            this.data = data;
            this.nextNode = null;
        }
        
    }
    
    // index 위치의 노드 데이터를 반환한다.
    public Object get(int index){
        return getNode(index).data;
    }
    
    // index 위치의 노드를 반환한다.
    private Node getNode(int index){
        
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("Index : " + index + ", Size : " + size);
        }
        
        Node node = header.nextNode;
        for(int i =0; i < index; i++){
            node = node.nextNode;
        }
        
        return node;
    }
    
    // 첫번째 노드의 데이터를 반환한다.
    public Object getFirst(){
        return get(0);
    }
    
    // 해당 데이터의 노드 위치 index를 반환한다.
    public int getNodeIndex(Object obj){
        
        if(size<=0){
            return -1;
        }
        
        int index=0;
        Node node = header.nextNode;
        Object nodeData = node.data;
        
        // header에서 부터 순차적으로 nodeData와 값을 비교한다.
        while(!obj.equals(nodeData)){
            node = node.nextNode;
            
            if(node==null){
                return -1;
            }
            
            nodeData = node.data;
            index++;
        }
        
        return index;
    }
    
    // data를 리스트의 첫번째에 삽입한다.
    public void addFirst(Object data){
        
        Node newNode = new Node(data);
        newNode.nextNode = header.nextNode;
        header.nextNode = newNode;
        size++;
        
    }
    
    // index 위치에 data를 삽입한다.
    public void add(int index, Object data){
        
        if(index==0){
            addFirst(data);
            return;
        }
        
        Node previous = getNode(index-1);
        Node next = previous.nextNode;
        
        Node newNode = new Node(data);
        previous.nextNode = newNode;
        newNode.nextNode = next;
        size++;
    }
    
    // 리스트의 마지막에 data 를 삽입한다.
    public void addLast(Object data){
        add(size, data);
    }
    
    // 리스트의 마지막에 data를 삽입한다.
    public void add(Object data){
        addLast(data);
    }
    
    // 첫번째 노드를 제거하고 데이터를 반환한다.
    public Object removeFirst(){
        
        Node firstNode = getNode(0);
        header.nextNode = firstNode.nextNode;
        size--;
        return firstNode.data;
        
    }
    
    // index 위치의 노드를 제거하고 데이터를 반환한다.
    public Object remove(int index){
        
        if(index<0 || index>=size){
            
            throw new IndexOutOfBoundsException("Index : " + index + ", Size : " +size);
        
        }else if(index ==0){
            
            return removeFirst();
        
        }
        
        Node previous = getNode(index-1);
        Node removeNode = previous.nextNode;
        Node next = removeNode.nextNode;
        previous.nextNode = next;
        size--;
        
        return removeNode.data;
    }
    
    // 리스트에서 data를 가진 노드를 제거하고 제거여부를 반환한다.
    public boolean remove(Object data){
        
        int nodeIndex = getNodeIndex(data);
        
        if(nodeIndex == -1){
            return false;
        }else{
            remove(nodeIndex);
            return true;
        }
    }
    
    // 리스트의 마지막 노드를 제거하고 데이터를 반환한다.
    public Object removeLast(){
        return remove(size-1);
    }
    
    // 리스트의 크기를 반환한다.
    public int size(){
        return size;
    }
    
    // 리스트의 데이터 String으로 반환
    public String toString(){
        
        StringBuffer result = new StringBuffer("[");
        Node node = header.nextNode;
        
        if(node!=null){
            result.append(node.data);
            node = node.nextNode;
            
            while(node != null){
                result.append(", ");
                result.append(node.data);
                node = node.nextNode;
            }
        }
        
        result.append("]");
        return result.toString();
    }

}

출처: https://hyeonstorage.tistory.com/259 [개발이 하고 싶어요]

 

---

 

이중 연결 리스트

출처 : https://hyeonstorage.tistory.com/261

출처 : https://hyeonstorage.tistory.com/261

이중 연결 리스트(Doubly Linked List)는 다음 노드의 참조 뿐만 아니라 이전 노드의 참조도 같이 가리키게 하는 리스트이다. 뒤로 탐색하는 게 빠르다는 단순한 장점 이외에도 한 가지 장점이 더 있다. 단순 연결 리스트는 현재 가리키고 있는 노드를 삭제하는게 한 번에 안 되고, O(n)이 될 수 밖에 없는데 비해 이중 연결 리스트에서 현재 노드를 삭제하는 것은 훨씬 간단하다. 반면, 관리해야 할 참조가 두 개나 있기 때문에 삽입이나 정렬의 경우 작업량이 더 많고 자료구조의 크기가 약간 더 커진다. 이 구조는 단일 연결 리스트보다는 손상에 강하다. Next와 Prev 노드를 가지고 있다면 둘 중 하나를 가지고 전체 리스트를 순회할 수 있기 때문에 끊어진 체인을 복구하는게 가능하다. 

Java로 구현된 이중 연결 리스트는 다음과 같다.

public class DoublyLinkedList {
    
    private Node header;
    private int size;
    public DoublyLinkedList(){
        header = new Node(null);
        size=0;
    }
    
    
    private  class Node{
        
        private Object data;
        private Node previousNode;
        private Node nextNode;
        
        Node(Object data){
            
            this.data = data;
            this.previousNode = null;
            this.nextNode = null;
            
        }
    }
    
    // index위치에서 얻은 노드의 데이터를 반환한다.
    public Object get(int index){
        return getNode(index).data;
    }
    
    // 첫번째 노드를 반환한다.
    public Object getFirst(){
        return get(0);
    }

    
    private Node getNode(int index){
        
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index : "+index+", Size : " + size);
        }
        
        Node node = header;
        
        // index 가 리스트 size의 중간 앞이면 순차적으로 탐색한다.
        if(index < (size/2)){
            
            for(int i =0; i<=index; i++){
                node = node.nextNode;
            }
            
        }else{
            // index가 리스트 size의 중간보다 뒤면 뒤에서부터 탐색한다.
            for(int i = size; i > index; i--){
                node = node.previousNode;
        
            }
        }
        
        return node;
    }
    
    // obj 데이터와 같은 노드의 위치를 반환한다.
    private int getNodeIndex(Object obj){
        
        if(size<=0){
            return -1;
        }
        
        int index =0;
        // 첫번째 노드를 가져온다.
        Node node = header.nextNode;
        Object nodeDate = node.data;
        
        // 첫번째 노드부터 같은 데이터를 가진 노드를 탐색한다.
        while(!obj.equals(nodeDate)){
            
            node = node.nextNode;
            
            if(node==null){
                return -1;
            }
            
            nodeDate = node.data;
            index++;
        }
        
        // 위치를 반환한다.
        return index;
    }
    
    // 리스트의 첫번째에 데이터를 삽입한다.
    public void addFirst(Object data){
        
        // 데이터를 담은 새로운 노드 생성
        Node newNode = new Node(data);    
        
        // 새로운 노드가 다음 노드로 첫번째 노드를 가리킨다.
        newNode.nextNode = header.nextNode;    
        
        // 리스트가 비어있지 않으면
        if(header.nextNode != null){
            
            // 첫 노드가 자신의 앞 노드로 새로운 노드를 가리킨다..
            header.nextNode.previousNode = newNode;
        
        }else{    // 리스트가 비어있으면
            
            // 헤더가 마지막 노드를 새로운 노드로 가리키도록 한다.
            header.previousNode = newNode;
        
        }
        
        // 헤더가 첫번째 노드로 새로운 노드를 가리키도록 한다.
        header.nextNode = newNode;
        size++;
    }
    
    public void add(int index, Object data){
        
        // index가 0 이면 addFirst() 함수를 호출한다.
        if(index ==0){
            
            addFirst(data);
            return;
        }
        
        // 삽입할 index 위치의 앞 노드를 가져온다.
        Node previous = getNode(index-1);
        
        // 삽입할 index의 위치의 다음 노드를 가져온다.
        Node next = previous.nextNode;
        
        // data로 새로운 노드 생성
        Node newNode = new Node(data);
        
        // 앞노드가 새로운 노드를 다음노드로 가리킨다.
        previous.nextNode = newNode;
        
        // 새로운 노드가 앞노드를 이전노드로 가리킨다.
        newNode.previousNode = previous;
        
        //새로운 노드의 다음 노드에 다음노드를 지정한다.
        newNode.nextNode = next;
        
        // 삽입 위치가 마지막 위치가 아니면
        if(newNode.nextNode != null){
            
            // 다음 노드가 새로운 노드를 앞노드로 지정한다.
            next.previousNode = newNode;
        
        }else{ // 삽입 위치가 마지막 이면
            
            // 헤더가 가리키는 마지막 노드가 새로운 노드가 된다..
            header.previousNode = newNode;
        }
        
        size++;
    }
    
    // 마지막 노드를 반환한다.
    public void addLast(Object data){
        add(size, data);
    }
    
    //data를 마지막에 넣는다.
    public void add(Object data){
        addLast(data);
    }
    
    public Object removeFirst(){
        
        // 첫번째 노드를 가져온다.
        Node firstNode = getNode(0);
        
        // 헤더가 첫 노드로 두번째 노드를 가리킨다.
        header.nextNode = firstNode.nextNode;
        
        // 리스트가 비어있지 않을 때
        if(header.nextNode != null){
            
            // 두번째 노드가 가리키는 앞 노드는 없다.
            firstNode.nextNode.previousNode = null;
        
        }else{ // 리스트가 비게 되면
            
            // 헤더가 가리키는 마지막 노드가 없다.
            header.previousNode = null;
            
        }
        
        size--;
        // 첫번째 노드의 데이터를 반환
        return firstNode.data;
    }

    public Object remove(int index){
        
        if(index<0 || index>=size){
            throw new IndexOutOfBoundsException("Index : " + index + ", Size : " + size);
        }else if(index==0){
            return removeFirst();    // index가 0 이면 첫번째 데이터 제거
        }
        
        // 제거할 index 위치의 노드를 가져온다.
        Node removeNode = getNode(index);
        // 제거할 노드의 앞노드를 가져온다.
        Node previous = removeNode.previousNode;
        // 제거할 노드의 뒷노드를 가져온다.
        Node next = removeNode.nextNode;
        
        // 앞노드가 다음노드를 다음으로 가리킨다.
        previous.nextNode = next;
        
        // 제거되는 노드가 마지막 노드가 아니면
        if(next!=null){
            
            // 제거 노드의 뒷노드가 앞노드로  제거 노드 앞 노드를 가리킨다.
            next.previousNode = previous;
            
        }else{ // 제거 노드가 마지막 노드면
            
            // 헤더가 마지막 노드로 앞노드를 가리킨다.
            header.previousNode = previous;
            
        }
        
        size--;
        
        // 제거노드의 데이터를 반환
        return removeNode.data;
    }
    
    // 데이터를 제거한다.
    public boolean remove(Object data){
        
        // data가 있는 index를 얻는다.
        int nodeIndex = getNodeIndex(data);
        
        // 데이터가 없으면 false 반환ㄷ
        if(nodeIndex == -1){
            return false;
        }else{ // 데이터가 있으면 제거
            remove(nodeIndex);
            return true;
        }
    }

    public Object removeLast(){
        return remove(size-1);
    }
    
    public int size(){
        return size;
    }
    
    public String toString(){
        
        StringBuffer result = new StringBuffer("[");
        Node node = header.nextNode;
        
        if(node != null){
            result.append(node.data);
            node = node.nextNode;
            
            while(node!=null){
                result.append(", ");
                result.append(node.data);
                node = node.nextNode;
            }
        }
        
        result.append("]");
        return result.toString();
    }

}

출처: https://hyeonstorage.tistory.com/261?category=578561 [개발이 하고 싶어요]

 

---

 

원형 연결 리스트

출처 : geeksforgeeks

원형 연결 리스트(Circular Linked List)는 단순 연결 리스트와 이중 연결 리스트에서 모두 구현이 가능하다. 단순 연결 리스트에서 마지막 원소가 NULL 대신 처음 원소를 가리키게 하면 원형 연결 리스트가 된다. 비슷한 방법으로, 이중 연결 리스트의 처음과 끝을 서로 이으면 이중 원형 연결 리스트를 만들 수 있다. 이는 스트림 버퍼 구현에 많이 사용이 되고, 할당된 메모리 공간을 삭제하고 재할당 하는 부담이 없기 때문에 큐를 구현하는 데에도 적합하다.

C로 구현된 원형 연결 리스트는 다음과 같다.

/*
원형 연결 리스트 (Circular Linked List)
*/
#include 
#include 

#define null NULL

typedef struct node{
	int data;
	node* next;
}Node;

typedef struct list{
	int countIndex;
	Node* tail;				// 원형리스트는 head가 아닌 tail노드를 가진다.
}List;

List* CreateList(){
	List* list = (List*)malloc(sizeof(List));

	if(list == null)
	{
		printf("error\n");
	}
	else
	{
		list->tail = null;
		list->countIndex = 0;
	}

	return list;
}

void AddNode(List* list, int position, node element){
	Node *preNode = list->tail;
	Node *newNode = (Node*)malloc(sizeof(Node));

	//데이터 삽입
	newNode->data = element.data;

	if(list->countIndex == 0)
	{
		newNode->next = newNode;
		list->tail = newNode;
	}
	else
	{
		for(int i = 0; i < position; i++)
		{
			preNode = preNode->next;
		}

		newNode->next = preNode->next;
		preNode->next = newNode;

		if(position == list->countIndex)
		{
			list->tail = newNode;
		}
	}

	list->countIndex++;
}

void DelNode(List* list, int position){
	Node *preNode = list->tail;
	Node *delNode = list->tail;

	
	if(list->countIndex == 0)
	{
		printf("노드가 없습니다.");
	}
	else
	{
		for(int i = 0; i < position; i++)
		{
			preNode = preNode->next;
		}

		delNode = preNode->next;
		preNode->next = delNode->next;
		free(delNode);
		
		if(position == list->countIndex-1)
		{
			list->tail = preNode;
		}

		list->countIndex--;
	}
}

void display(List* list){
	int i;
	Node* node;

	for(node = list->tail->next, i = 0; i < list->countIndex; i++, node = node->next){
		printf("%d ", node->data);
	}
}


출처: https://supark7.tistory.com/entry/원형-연결-리스트-Circular-Linked-List [배우는 즐거움]

 

참고자료

1. https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure
2. https://hyeonstorage.tistory.com/259
3. https://www.geeksforgeeks.org/data-structures/linked-list/
4. https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8
5. https://supark7.tistory.com/entry/%EC%9B%90%ED%98%95-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-Circular-Linked-List
6. <코딩인터뷰 완전분석>, 게일 라크만 맥도웰 저
7. <C언어로 쉽게 풀어쓴 자료구조>, 천인국 외 저