[자료구조] 순차 리스트 ( Sequential List )

 

미리 알림

내용 읽다 보시면 이거 배열이랑 다를게 뭐야.. 라고 생각하실텐데,

배열이란 길이가 한정적인 연속된 자료구조 입니다.

하지면 저희가 쓰는 Swift 의 Array 는 길이가 유동적입니다.

그래서 Array 는 순차 리스트의 일종이구나~ 하고 봐주시면 됩니다.

---

 

 

데이터를 연속해서 저장하는 자료구조입니다.

순차 리스트의 가장 큰 특징은 데이터를 메모리 상에 연속된 위치에 저장한다. 입니다.

데이터의 추가, 제거에 오버헤드가 발생하지만, 인덱스를 사용해 데이터에 빠르게 접근이 가능합니다.

 

데이터는 어디에서나 추가가 가능하므로,

append 의 경우 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다.

insert 의 경우 데이터의 추가는 O(N) 의 시간복잡도를 갖습니다.

 

데이터는 어디에서나 제거가 가능하므로,

remove 의 경우 데이터의 제거는 O(n) 의 시간복잡도를 갖습니다.

 

Sequential List 를 이해하기 쉽게 그림으로 나타내면 아래와 같습니다.

순차 리스트_001

아래 그림과 같이 동작하게 됩니다.

insert(item: ,index: )	Sequential List 의 index 위치에 item 을 추가합니다.
remove(index: )	Sequential List 의 index 위치의 item 을 제거합니다.
add(item: )	Sequential List 의 가장 뒤쪽에 item 을 추가합니다.

 

순차리스트_002

---

 

구현

 

Sequential List 는 Swift 를 사용하여 아래와 같이 구현하며, 아래와 같이 사용할 수 있습니다.

//MARK: Sequential List 구현
class SequentialList<T> {
    
    private var capacity: Int  // 리스트 크기
    private var count: Int = 0 // 현재 리스트에 저장된 요소 수
    private var buffer: UnsafeMutablePointer<T> // 요소를 저장하는 메모리 버퍼

    
    init(capacity: Int) {
    // Sequential List 를 초기화 합니다
        self.capacity = max(capacity, 1) // 최소한 1개 이상의 요소를 저장할 수 있도록 함
        buffer = UnsafeMutablePointer<T>.allocate(capacity: capacity)
    }

    deinit {
    // Sequential List 를 메모리에서 해제합니다.
        buffer.deallocate()
    }

    
    var isEmpty: Bool {
    // Sequential List 가 비어있는지 true/ false 를 반환합니다.
        return count == 0
    }

    
    var size: Int {
    // Sequential List 의 길이를 반환합니다.
        return count
    }


    func append(_ newElement: T) {
    // Sequential List 의 가장 마지막에 데이터를 추가합니다.
        if count == capacity { // 리스트가 꽉 찬 경우
            let newCapacity = capacity * 2 // 두 배 크기로 확장
            let newBuffer = UnsafeMutablePointer<T>.allocate(capacity: newCapacity)
            for i in 0..<count {
                newBuffer[i] = buffer[i]
            }
            buffer.deallocate()
            buffer = newBuffer
            capacity = newCapacity
        }
        buffer[count] = newElement
        count += 1
    }

    
    func insert(_ newElement: T, at index: Int) {
    // Sequential List 의 index 위치에 데이터를 추가합니다.
        if index < 0 || index > count {
            fatalError("Index out of range")
        }
        if count == capacity { // 리스트가 꽉 찬 경우
            let newCapacity = capacity * 2 // 두 배 크기로 확장
            let newBuffer = UnsafeMutablePointer<T>.allocate(capacity: newCapacity)
            for i in 0..<count {
                newBuffer[i] = buffer[i]
            }
            buffer.deallocate()
            buffer = newBuffer
            capacity = newCapacity
        }
        for i in stride(from: count-1, through: index, by: -1) {
            buffer[i+1] = buffer[i]
        }
        buffer[index] = newElement
        count += 1
    }

    func remove(at index: Int) -> T {
    // Sequential List 의 index 위치의 데이터를 제거합니다.
        if index < 0 || index >= count {
            fatalError("Index out of range")
        }
        let result = buffer[index]
        for i in index..<count-1 {
            buffer[i] = buffer[i+1]
        }
        count -= 1
        return result
    }

    subscript(index: Int) -> T {
    // Sequential List 의 index 위치의 데이터를 반환합니다.
        get {
            if index < 0 || index >= count {
                fatalError("Index out of range")
            }
            return buffer[index]
        }
        set(newValue) {
            if index < 0 || index >= count {
                fatalError("Index out of range")
            }
            buffer[index] = newValue
        }
    }
}



var mSList = SequentialList<Int>(capacity: 10)

mSList.isEmpty	// 비어있는지 확인
mSList.size		// 길이 확인

mSList.append(10)	// 데이터 추가, 뒤
mSList.append(20)	// 데이터 추가, 뒤
mSList.append(30)	// 데이터 추가, 뒤
mSList.insert(40, at: 1)	// 데이터 추가, index 위치

mSList.remove(at: 2)	// 데이터 제거, index 위치
mSList.remove(at: 1)	// 데이터 제거, index 위치

 

... Array 사용하시면 됩니다^^.

 

P.S

추가적으로 생각나거나 찾은 내용은 날짜를 덧붙여 업데이트 하겠습니다.