[자료구조] Linked List

자료구조 03 / Linked List

---

정의 

연결 리스트는 배열과 달리 떨어진 곳에 존재하는 데이터를 각 주소끼리 연결하는 데이터 구조

(배열 : 순차적으로 연결된 공간에 데이터를 나열 하는 데이터 구조)

 

파이썬, 스위프트 등의 최근 고급 언어에서는 배열 자체도 동적으로 할당받을 수 있어서

(연결 리스트 형태와 유사하게 동작하기도 한다)

 

Linked List는 노드 (Node)의 묶음으로 볼 수 있는데

Node는 값을 갖는 Data와 다음 노드를 가리키는 포인터(Pointer)를 포함함

참조 (https://www.raywenderlich.com/947-swift-algorithm-club-swift-linked-list-data-structure)

Node를 Class로 구현하는 경우 클래스의 객체를 = 할당하는 건 참조(포인터 연결)와 같은 기능을 하기 때문에

C/C++ 언어와 달리 Swift는 따로 포인터 없이 객체를 바로 할당한다.

 

github

GitHub - keeplo/SwiftTools: 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제

구현 

Node 구현

// Swift 5
// raywenderlich.com

class Node {
    let data: Int
    var next: Node?

    init(data: Int) {
        self.data = data
    }
}

- 노드에 하나의 노드만 이어지므로 next 하나의 포인터만 존재

 

노드 추가

class LinkedList {
    // 리스트 끝에 데이터 추가
    func append(head: Node?, data: Int) -> Node? {
        if head == nil {
            return Node(data: data)
        }

        head?.next = append(head: head?.next, data: data)

        return head
    }
}

- head에서 가장 마지막 노드까지 이동 후 추가할 노드를 연결

 

마지막 노드 제거

class LinkedList {
    // 마지막 노드 제거
    func removeLast(head: Node?) -> Node! {
        if head?.next == nil {
           return nil
        }
        var current = head
        
        while current?.next?.next != nil {
            current = current!.next
        }
        
        current!.next = nil
        
        return head
    }
}

- head에서 가장 마지막 노드의 직전까지 이동 후 마지막 노드를 제거

 

프린트 리스트

class LinkedList {
    // Linked List 전체 프린트
    func display(head: Node?) {
        if head != nil {
            print(head!.data, terminator: " ")

            display(head: head?.next)
        } else {
            print("/")
        }
    }
}

- head부터 다음노드로 넘어가면서 순서데로 데이터를 print 함

 

중복 제거

class LinkedList {
    // 중복 제거
    func removeDuplicatesCheck(head: Node?) {
        var current = head
        var datas = [Int]()

        while current?.next != nil {
            datas.append(current!.data)

            if current?.next?.next != nil, datas.contains((current?.next?.data)!) {
                current?.next = current?.next?.next
            } else {
                if datas.contains((current?.next?.data)!) {
                    current!.next = nil
                } else {
                    current = current!.next
                }
            }
        }
    }
}

- Linked List를 타고 가며 각 노드의 데이터를 배열에 순차적으로 넣으면서 배열에 다음 노드의 데이터가 존재하면 건너뛰고 다다음 노드를 이어감 마지막 노드의 데이터가 중복되면 마지막 노드는 nil

 

 

n번째자리 노드 추가

class LinkedList {
    // 원하는 순서에 데이터 추가
    func insert(head: Node?, index: Int, data: Int) -> Node {
        var current = head
        let newNode = Node(data: data)
        
        if index != 0 {
            for _ in 0..<index {
                current = current?.next
            }
            newNode.next = current?.next
            current = newNode
            return head!
        } else {
            newNode.next = current?.next
            return newNode
        }
    }
}

- for문을 이용해서 원하는 index 만큼 노드를 건너뛰고 새로운 노드를 현재노드와 다음노드에 이어줌 

 

n번째자리 노드 삭제

class LinkedList {
	// 원하는 순서 노드 삭제
    func removeAt(head: Node?, index: Int) -> Node! {
        var current = head
        
        if head?.next == nil {
            return nil
        } else if index == 0 {
            return current!.next
        } else {
            for _ in 0..<index-1 {
                current = current?.next
            }
            current?.next = current?.next?.next
        }
        
        return head
    }
}

- 원하는 인덱스 직전까지 노드를 접근해서 다음 노드를 다다음 노드로 이어줌

 

예제

https://www.hackerrank.com/challenges/30-linked-list/problem

추가적으로 생각해 볼 내용

자료의 추가와 삭제 동작이 중간 지점에서 일어나도 O(1)의 시간에 가능하다 (배열처럼 index의 이동이 없다)

단점은 배열이나 트리구조와 달리 특정위치의 데이터 검색을 위해 O(n)의 시간이 걸린다.

 

Reference : raywenderlich.com github explain