자료구조 : 연결 리스트를 이해해보아요.

Jhoon·2022년 11월 10일

알고리즘 연결리스트 자료구조

자료구조: 연결리스트

목록 보기

1/4

이 게시물은 개인적 공부를 위해 작성한 글입니다. 이해한 내용을 기반으로 정리하고자 쓰는 글이니 틀린내용이 있을수 있습니다.

Data structure 는 뭔가 어려워 보인다.
하지만 어떠한 방식으로 이용되고, 왜 사용되는지 알게 된다면 어려움도 이해가 될것이다.

자 먼저 연결 리스트 를 이해해보자.

연결 리스트를 이해해 보아요.

순차 자료구조 방식은 배열을 이용하여 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가지고 있다.
- 자바로 배우는 쉬운 자료구조 p198

여기서 말하는 순차 자료구조 방식은 일반적인 배열구조를 말한다.

순차적 자료구조란?

배열이 있다면 순서대로 메모리가 생성된다.
만약 다음처럼 배열이 있다고 생각해보자.

int arr[] = {1, 2, 3, 4}; // int 배열

각 메모리는 1byte 를 가지며, 위 배열의 시작 메모리주소는 0x100 이라 가정한다.

0X100 에서 부터 시작하며, int 는 4byte 이므로 배열의 0 번째 int 값은 0x103 까지의 메모리 주소를 가진다.

다음 1번째 index는 0x104 부터 시작하며,
다음 2번째 index는 0x108 부터 시작하며,
다음 3번째 index눈 0x10C 부터 시작하고 0x110에서 끝난다.

각각의 메모리 주소를 연결하여 순차적으로 나열하기 때문에 이를 순차 자료구조 방식 이라 한다.

위에서는 0x100 에서 0x110 까지 메모리를 확보한후 각 data 값을 할당한다.

그래서 뭐가 문제인데?

이는 배열의 값을 메모리에 순서대로 유지한다는것이 문제이다.

배열 중간에 값을 삽입해보자.


const arr:number[] = [1, 3, 4];
arr.splice(1, 0, 2);

위를 순차 자료구조 방식으로 설명하면 다음 처럼 작동한다.

3번째 index 를 생성한다.
2번째 index 를 3번째 index 에 값을 삽입 한다.
1번째 index 를 2번째 index 에 값을 삽입 한다.
마지막으로 1번째 index 의 값에 2 를 삽입한다.

이처럼 원소들의 순서를 유지하기 위해 물리적(메모리상에서의 주소)으로 뒤로 밀어낸후 값을 삽입하기에 추가적인 오버해드가 발생한다.

이렇게 연속된 메모리 주소를 통해 원소의 값을 가지지 않고, 순서를 유지할 수 있는 개선된 리스트를 사용한다면 더 좋을 것이다.

그렇다면 어떠한 방식으로 개선할수 있을까?

이는 바로 메모리 참조값을 사용하여 서로와 서로를 Link 시키는 방법이다.

이것이 Linked List 다.

다음을 보자.

export interface Node {
    data: string
    link: Node | null
}

export type NodeType = Node | null

객체는 Node type 객체이다.
Node 객체에는 link property 가 존재한다.

link property 는 자신의 다음 참조할 객체의 주소를 가진다.

이렇게 참조 주소를 property 로 갖고 각 객체를 순서대로 반환한다면 data 를 배열의 원소처럼 사용할 수 있다.

밑의 NodeType 타입이 Node 또는 null 일수 있도록 지정해둔 지정 타입이라 생각하면 된다.

LinkedList 자체에서는 그다지 중요한 내용은 아니니 넘어가도 된다.


{data: "월", link: 0x100}: Node // 객체 주소: 0x600
--> {data: "수", link: 0x210}: Node // 겍체 주소: 0x100
--> {data: "일", link: null}: Node // 객체 주소: 0x210

순차 자료구조 방식 과는 다르게 추가적으로 link property 라는 추가저장공간이 필요지만, 순차적으로 메모리주소를 관리할 필요가 없기 때문에 원소 삽입 및 삭제의 오버헤드가 없어진다.

다음을 보자.

// LinkedList.ts

export class LinkedList {
    constructor(private head: NodeType = null) {}

    public insertLastNode(data: string) {
        const newNode: Node = { data, link: null }
        if (this.head == null) this.head = newNode 
        else {
            let tmp: Node | null = this.head
            while(tmp.link != null) {
                tmp = tmp.link
            }
            tmp.link = newNode
        }
    }

    public insertMiddleNode(pre: NodeType, data: string) {
        console.log(pre);
        if (pre == null) return
        const newNode: Node = { data, link: null }
        newNode.link = pre.link
        pre.link = newNode
    }

    public deleteLastNode() {
        if (this.head == null) return
        if (this.head.link == null) { this.head = null }
        else {
            let pre: Node = this.head
            let tmp: Node = this.head.link
            while( tmp.link != null ) {
                pre = tmp
                if (pre.link != null) tmp = pre.link
            }
            pre.link = null
        }
    }

    public searchNode(data: string) {
        if (this.head == null) return null; 
        let tmp: Node = this.head
        while(tmp.link != null) {
           if (tmp.data == data) return tmp
           tmp = tmp.link
        }
        return tmp
    }

    public printList() {
        if (this.head == null) return
        let tmp: Node = this.head
        while( tmp.link != null ) {
            process.stdout.write(`${tmp.data}, `)
            tmp = tmp.link
        }
        process.stdout.write(`${tmp.data}\n`)
    }

    public reverseNode() {
        if (this.head == null) return
        if (this.head.link == null) return
        let pre: NodeType = null
        let cur: NodeType = null
        let next: NodeType = this.head

        while(next != null) {
            cur = next
            next = next.link
            cur.link = pre
            pre = cur
        }
        this.head = cur
    }
}

// index.ts
import { NodeType, LinkedList } from "./LinkedList"

const L: LinkedList = new LinkedList();
L.insertLastNode('월')
L.insertLastNode('수')
L.insertLastNode('금')
L.printList() // 월, 수, 금