[자료구조] 연결리스트

1. 단일 연결리스트

연결리스트는 배열과 달리 연속된 공간에 위치하지 않고 한요소가 다음 요소를 가리키는 구조를 가지고 있습니다. 즉 한 요소가 자신의 데이터와 연결된 요소의 주소값을 가지고 있는것입니다.

 

이러한 특징때문에 인덱스만 알면 바로 값을 탐색할 수 있는 배열과 달리 특정한 값을 찾기위해서는 그 전의 모든 요소를 순회해야 합니다. 이와는 달리 삽입과 삭제는 주소값만 변경하면 되므로 삽입하거나 삭제할 요소까지 접근하는 시간을 제외하면 매우 빠릅니다.

 

따라서 연결리시트는 삽입과 삭제에 있어서는 처음, 중간, 끝에 따라 다른 시간복잡도를 가집니다. 

 

처음(헤드)과 끝(테일)을 삽입하거나 삭제할때는 O(1)의 시간복잡도가 걸리며 중간에 삽입하거나 삭제할때는 O(n)의 시간복잡도가 걸립니다. 다만 중간값이라도 배열의 삽입, 삭제보다는 시간이 덜걸립니다. 왜냐하면 배열처럼 값의 이동이 없으며 삽입하거나 삭제할 요소를 찾는데 O(n)의 시간이 걸리며 요소를 찾고나면 O(1)의 시간이 걸리기 때문입니다. 즉, 반복문에서 break를 거는것과 비슷합니다.

 

이를 예시코드로 보여드리면 아래와 같습니다.

 

파이썬

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None # 다음 노드의 주소값

class SinglyLinkedList:
    def __init__(self):
        self.head = None
	
    # 헤드에 노드를 추가하는 메서드 -> 시간복잡도 O(1)
    def insert_at_head(self, data):
        new_node = Node(data) # 매개변수로 data를 받아서 새로운 노드를 만듬
        new_node.next = self.head # 다음노드의 주소값은 None (헤드를 먼저 만드므로)
        self.head = new_node # head 값에 새로운 노드를 넣음
	
    # 요소를 추가하는 메서드 -> 시간복잡도 O(n)
    def insert_at_position(self, data, position):
        if position == 0: # 위치가 0이라면 헤드 추가
            self.insert_at_head(data)
            return
        new_node = Node(data) # 새로운 노드 생성
        current = self.head # current의 헤드의 주소값을 넣음
        for _ in range(position - 1):
            if current is None:
                return  # position out of bounds
            current = current.next # 다음 주소값이 있다면 원하는 포지션까지 계속 찾아감
        if current is None:
            return
        new_node.next = current.next  # 새 요소는 다음 요소를 가리키도록 하고
        current.next = new_node # 이전 요소는 새 요소를 가리키도록 함
	
    # 요소를 삭제하는 메서드 -> 시간복잡도 O(n)
    def delete(self, key):
        current = self.head
        prev = None # prev는 current요소의 이전 요소로 current가 제거되었을때 prev의 다음 주소값으로 current의 다음 주소값을 저장하기 위함
        while current:
            if current.data == key:
                if prev:
                    prev.next = current.next
                else:
                    self.head = current.next
                return
            prev = current
            current = current.next

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

ll = SinglyLinkedList()

ll.insert_at_head(17)
ll.insert_at_head(18)
ll.insert_at_head(19)
ll.insert_at_head(76)
ll.insert_at_head(44)


ll.insert_at_position(34, 3)

ll.delete(18)

print(ll.search(19)) # True

ll.traverse()
# 44 -> 76 -> 19 -> 34 -> 17 -> None

 

자바

class Node {
    int data;
    Node next; // 다음 노드의 주소값
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SinglyLinkedList {
    Node head; //head 선언 -> 값은 null
	
    //헤드에 노드를 추가하는 메서드 -> 시간복잡도 O(1)
    public void insertAtHead(int data) {
        Node newNode = new Node(data); // 매개변수로 data를 받아와서 새로운 노드를 만듬
        newNode.next = head; //새로운 노드의 다음 주소값으로 null을 넣음
        head = newNode; // 헤드를 새로운 노드로 변경
    }
	
    //요소를 추가하는 메서드-> 시간복잡도 O(n)
    public void insertAtPosition(int data, int position) {
        if (position == 0) { //위치가 0이라면 헤드 추가
            insertAtHead(data);
            return;
        }
        Node newNode = new Node(data); //새로운 노드를 생성하고
        Node current = head; //현재 노드에 헤드 주소를 넣음
        for (int i = 0; i < position - 1 && current != null; i++) {
            current = current.next; // 원하는 포지션까지 다음 주소값을 찾아감
        }
        if (current == null) return;
        newNode.next = current.next; //새 요소는 다음 요소를 가리키도록 하고
        current.next = newNode; // 이전 요소는 새 요소를 가리키도록 함
    }
	
    //요소를 삭제하는 메서드 -> 시간복잡도 O(n)
    public void delete(int key) {
    	//prev는 current를 제거했을때 이전 요소 다음 주소값으로 current의 다음 주소값으로 바꾸기 위함
        Node current = head, prev = null; 
        while (current != null) {
            if (current.data == key) {
                if (prev != null) {
                    prev.next = current.next;
                } else {
                    head = current.next;
                }
                return;
            }
            prev = current;
            current = current.next;
        }
    }

    public boolean search(int key) {
        Node current = head;
        while (current != null) {
            if (current.data == key) return true;
            current = current.next;
        }
        return false;
    }

    public void traverse() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        
        SinglyLinkedList ll = new SinglyLinkedList();
        
        ll.insertAtHead(17);
        ll.insertAtHead(18);
        ll.insertAtHead(19);
        ll.insertAtHead(76);
        ll.insertAtHead(44);
        
        ll.insertAtPosition(34, 3);
        
        ll.delete(18);
        
        System.out.println(ll.search(19)); // true
        
        ll.traverse();
        // 44 -> 76 -> 19 -> 34 -> 17 -> null
    }
}

 

2. 이중연결리스트

이중연결 리스트는 각 요소가 이전요소의 주소값, 다음요소의 주소값을 모두 가지고 있습니다. 따라서 정방향으로만 작업이 가능한 단일 연결리스트와 달리 역방향으로도 작업이 가능합니다.

이러한 이유로 단일 연결리스트와는 달리 마지막(tail)에 값을 삽입하거나 삭제하는 것 O(1)의 시간복잡도를 가지게됩니다. 

그리고 중간에 삽입하거나 삭제하는 것도 앞에서 시작할지 뒤에서 시작할지를 정할 수 있기 때문에 빅오 표기법상 시간복잡도가 O(n)이지만 실제 시간은 더 적게 걸린다고 볼 수 있습니다.

 

이제 코드로 살펴보겠습니다.

 

파이썬

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None # 이전 주소값을 담을 prev 변수가 추가됨
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None # 마지막 노드 요소가 추가됨

    def insert_at_head(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
        # 앞 요소와 뒷 요소가 서로의 주소값을 가지고 있음
            new_node.next = self.head 
            self.head.prev = new_node 
            self.head = new_node
	
    # 맨 뒤의 요소를 넣는 메서드
    def insert_at_tail(self, data):
        new_node = Node(data)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def delete_from_head(self):
        if not self.head:
            return
        if self.head == self.tail: # 첫번째 노드와 마지막 노드가 같다는 것은 요소가 1개라는 의미
            self.head = self.tail = None # 헤드 노드와 테일 노드를 제거
        else:
            self.head = self.head.next
            self.head.prev = None

    def delete_from_tail(self):
        if not self.tail:
            return
        if self.head == self.tail:
            self.head = self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None

    def search_from_head(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def search_from_tail(self, key):
        current = self.tail
        while current:
            if current.data == key:
                return True
            current = current.prev
        return False

    def traverse_forward(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def traverse_backward(self):
        current = self.tail
        while current:
            print(current.data, end=" <- ")
            current = current.prev
        print("None")

dll = DoublyLinkedList()

dll.insert_at_head(14)
dll.insert_at_head(36)
dll.insert_at_head(61)
dll.insert_at_head(77)
dll.insert_at_head(22)

dll.insert_at_tail(48)

dll.delete_from_tail()

print(dll.search_from_tail(36)) # True

dll.traverse_forward()
# 22 -> 77 -> 61 -> 36 -> 14 -> None

dll.traverse_backward()
# 14 <- 36 <- 61 <- 77 <- 22 <- None

 

자바

class Node {
    int data;
    Node prev, next; // 이전 주소값을 담을 prev 변수가 추가됨
    Node(int data) {
        this.data = data;
    }
}

public class DoublyLinkedList {
    Node head, tail; //마지막 요소 노드가 추가됨

    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
        } else {
        // 앞요소와 뒷 요소가 서로의 주소값을 가지고 있음
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }
	
    // 맨뒤의 요소를 넣는 메서드
    public void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    public void deleteFromHead() {
        if (head == null) return;
        if (head == tail) { // 첫번재 노드와 마지막 노드가 같다는 것은 요소가 1개라는 의미
            head = tail = null; //헤드 노드와 테일 노드를 제거
        } else {
            head = head.next;
            head.prev = null;
        }
    }

    public void deleteFromTail() {
        if (tail == null) return;
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
    }

    public boolean searchFromHead(int key) {
        Node current = head;
        while (current != null) {
            if (current.data == key) return true;
            current = current.next;
        }
        return false;
    }

    public boolean searchFromTail(int key) {
        Node current = tail;
        while (current != null) {
            if (current.data == key) return true;
            current = current.prev;
        }
        return false;
    }

    public void traverseForward() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public void traverseBackward() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " <- ");
            current = current.prev;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
    
        DoublyLinkedList dll = new DoublyLinkedList();
        
        dll.insertAtHead(14);
        dll.insertAtHead(36);
        dll.insertAtHead(62);
        dll.insertAtHead(77);
        dll.insertAtHead(22);
        
        dll.insertAtTail(48);
        
        dll.deleteFromTail();
        
        System.out.println(dll.searchFromHead(36));
        // true

        dll.traverseForward();
        // 22 -> 77 -> 61 -> 36 -> 14 -> None
        
        dll.traverseBackward();
        // 14 <- 36 <- 61 <- 77 <- 22 <- None
    }
}

 

3. 원형연결리스트

원형 연결리스트는 말그대로 요소가 원형으로 연결되어있는 리스트를 의미합니다. 즉, 헤드와 테일이 연결되어있는 구조입니다.

원형 연결리스트 중에서도 단일 원형 연결리스트와 이중 원형 연결리스트가 있는데, 단일 원형 연결리스트는 테일의 다음 주소값이 헤드를 가리키고 있으며, 이중 원형연결리스트는 헤드와 테일이 서로의 주소값을 가지고 있습니다.

이러한 특징때문에 원형연결리스트에서는 무한순회가 가능합니다. 

다만 헤드나 테일이 있기 때문에 모든 작업의 시간복잡도는 단일 원형리스트는 단일 연결리스트와 동일하고, 이중 원형 연결리스트는 이중연결리스트와 동일합니다.

 

이를 코드로 확인해보겠습니다.

 

파이썬

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyCircularLinkedList:
    def __init__(self):
        self.head = None
        self.current = None

    def insert_at_head(self, data):
        new_node = Node(data)
        if not self.head:
            new_node.next = new_node.prev = new_node
            self.head = self.current = new_node
        else:
            tail = self.head.prev
            new_node.next = self.head
            new_node.prev = tail
            tail.next = self.head.prev = new_node
            self.head = new_node

    def insert_at_tail(self, data):
        new_node = Node(data)
        if not self.head:
            new_node.next = new_node.prev = new_node
            self.head = self.current = new_node
        else:
            tail = self.head.prev
            new_node.prev = tail
            new_node.next = self.head
            tail.next = self.head.prev = new_node


    def delete_from_head(self):
        if not self.head:
            return
        if self.head.next == self.head:
            self.head = self.current = None
            return
        tail = self.head.prev
        if self.current == self.head:
            self.current = self.head.next
        self.head = self.head.next
        self.head.prev = tail
        tail.next = self.head

    def delete_from_tail(self):
        if not self.head:
            return
        if self.head.next == self.head:
            self.head = self.current = None
            return
        tail = self.head.prev
        new_tail = tail.prev
        if self.current == tail:
            self.current = self.head
        new_tail.next = self.head
        self.head.prev = new_tail

    def move_next(self):
        if self.current:
            self.current = self.current.next

    def move_prev(self):
        if self.current:
            self.current = self.current.prev

    def print_current(self):
        if self.current:
            print("Current:", self.current.data)
        else:
            print("Current: None")

    def traverse_forward(self):
        if not self.head:
            print("Empty")
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("(head)")

    def traverse_backward(self):
        if not self.head:
            print("Empty")
            return
        current = self.head.prev
        while True:
            print(current.data, end=" <- ")
            current = current.prev
            if current == self.head.prev:
                break
        print("(tail)")


dll = DoublyCircularLinkedList()

dll.insert_at_tail(34)
dll.insert_at_tail(53)
dll.insert_at_tail(21)
dll.insert_at_tail(53)
dll.insert_at_tail(42)

dll.insert_at_head(64)
dll.delete_from_tail()

dll.traverse_forward()
# 64 -> 34 -> 53 -> 21 -> 53 -> (head)

dll.current = dll.head
dll.print_current() # 64

for i in range(8):
    dll.move_next()

dll.print_current() # 21

 

 

자바

class Node {
    int data;
    Node prev, next;
    Node(int data) {
        this.data = data;
    }
}

public class DoublyCircularLinkedList {
    Node head;
    Node current;

    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head.prev = head;
            current = head;
        } else {
            Node tail = head.prev;
            newNode.next = head;
            newNode.prev = tail;
            head.prev = tail.next = newNode;
            head = newNode;
        }
    }

    public void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head.prev = head;
            current = head;
        } else {
            Node tail = head.prev;
            newNode.prev = tail;
            newNode.next = head;
            tail.next = head.prev = newNode;
        }
    }


    public void deleteFromHead() {
        if (head == null) return;
        if (head.next == head) {
            head = current = null;
            return;
        }
        Node tail = head.prev;
        if (current == head) current = head.next;
        head = head.next;
        head.prev = tail;
        tail.next = head;
    }

    public void deleteFromTail() {
        if (head == null) return;
        if (head.next == head) {
            head = current = null;
            return;
        }
        Node tail = head.prev;
        if (current == tail) current = head;
        Node newTail = tail.prev;
        newTail.next = head;
        head.prev = newTail;
    }

    public void moveNext() {
        if (current != null)
            current = current.next;
    }

    public void movePrev() {
        if (current != null)
            current = current.prev;
    }

    public void printCurrent() {
        if (current != null)
            System.out.println("Current: " + current.data);
        else
            System.out.println("Current: null");
    }

    public void traverseForward() {
        if (head == null) {
            System.out.println("Empty");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(head)");
    }

    public void traverseBackward() {
        if (head == null) {
            System.out.println("Empty");
            return;
        }
        Node temp = head.prev;
        do {
            System.out.print(temp.data + " <- ");
            temp = temp.prev;
        } while (temp != head.prev);
        System.out.println("(tail)");
    }

    public static void main(String[] args) {
        DoublyCircularLinkedList dll
        = new DoublyCircularLinkedList();
        
        dll.insertAtTail(34);
        dll.insertAtTail(59);
        dll.insertAtTail(21);
        dll.insertAtTail(53);
        dll.insertAtTail(42);
        
        dll.insertAtHead(64);
        dll.deleteFromTail();
        
        dll.traverseForward();
        // 64 -> 34 -> 59 -> 21 -> 53 -> (head)

        dll.current = dll.head;
        dll.printCurrent(); // 64
        
        
        for (int i = 0; i < 8; i++) {
            dll.movePrev();
        }
        dll.printCurrent(); // 59
    }
}

 

 

 

참조: 얄코의 가장 쉬운 자료구조와 알고리즘
https://inf.run/Th7xU

얄코의 가장 쉬운 자료구조와 알고리즘| 얄팍한 코딩사전 - 인프런 강의