[자료구조]_연결리스트

hanseungjune·2023년 6월 14일
JavaJavaScriptpython
0

Computer Science

목록 보기
2/3
post-thumbnail

연결리스트란?

노드를 연결시킨 자료구조...

일단 그림을 보고 이해해보자

그림을 참고하면, data/text 하나가 노드이다. 그리고 연결된 것 처럼 다음 노드를 가리키고 있다. 저 화살표는 포인터를 의미한다고 한다.

특히, 제일 앞에 있는 노드는 헤드(head), 제일 끝 노드는 테일(tail)이라고 한다.

head와 tail의 data를 쓰지 않는다면, 추가, 삭제할 노드가 중간 노드인가 만 고려하면 된다.

왜 사용하는가?

  • 리스트의 길이가 가변적이다. (장점)
  • 배열은 우선 크기를 정해준 다음에 모자라면 메모리를 더 할당하고, 배열의 데이터를 복사해야 되죠. 오래걸리고 비효율적이다. (그래서 연결리스트 사용)

배열을 사용해서 필요에 따라 사이즈를 늘리는 코드

// java

int[] newList = new int[size * 2];
for (int i = 0; i < size; i++)
    newList[i] = list[i];
list = newList;
// js

let newList = new Array(size * 2);
for (let i = 0; i < size; i++)
    newList[i] = list[i];
list = newList;
# python

newList = [0] * (size * 2)
for i in range(size):
    newList[i] = list[i]
list = newList

해당 코드들은 메모리를 할당한 후 for 루프로 기존의 있던 값은 복사하는 것이다.
하지만 연결리스트는 다음 노드만 추가하면 끝.

왜 사용하지 않는가?

  • 연결리스트는 어떤 노드를 검색하거나 데이터를 변경할때 바로 찾아낼 수가 없습니다. (단점)
  • 링크드리스트를 전부 탐색해야할 수도 있습니다.
  • 데이터가 자주 추가되거나 가변적으로 자주 변하는 것이라면 연결리스트를 쓰는 것이 좋다.
  • 데이터의 가변적이지 않은 변경이나 탐색을 위한 것이라면 배열을 쓰는 것이 좋다.

연결리스트 연산 예시

  1. addFirst(list, data)
    링크드리스트의 새로운 노드를 추가합니다. 가장 앞에 있는 노드(head의 다음)에 새로운 노드를 추가하는 연산입니다.

  2. addLast(list, data)
    addFirst와 반대로 가장 뒤에 노드를 추가합니다.

  3. removeNode(list, data)
    링크드리스트가 갖고 있는 노드 중에 data값을 갖고 있는 노드를 삭제합니다.

  4. searchNode(list,data)
    링크드리스트에서 data의 값과 일치하는 노드를 검색합니다.

  5. printList()
    링크드리스트를 전부 탐색합니다. 리스트의 데이터를 전부 보여줍니다.

1. addFirst(list, data)

가장 첫번째에 노드를 추가합니다. 가장 첫번째라고 해서 head 앞에 추가해서는 안됩니다. head의 다음 노드에 추가해야합니다.
head의 다음 노드를 새로운 노드로 가리키게 만들고, 그 새로운 노드는 이전에 head가 가리키고 있던 노드를 가리키면 됩니다.

//java

public void addFirst(List list, int data) {
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = list.head.next;
    list.head.next = newNode;
    list.size++;
}
//js

function addFirst(list, data) {
    let newNode = {
        data: data,
        next: list.head.next
    };
    list.head.next = newNode;
    list.size++;
}

2. addLast(list, data)

가장 마지막(tail 앞)에 노드를 추가하는 연산입니다. 일단 tail앞까지 가야하지만, 그 전의 노드를 기억해야합니다. 그러니까 살짝 까다로울 수 있지요.

//java

public void addLast(List list, int data) {
    Node last = list.head;

    while (last.next != list.tail)
        last = last.next;

    Node newNode = new Node();
    newNode.data = data;
    newNode.next = list.tail;
    last.next = newNode;
    list.size++;
}
//js

function addLast(list, data) {
    let last = list.head;

    while (last.next !== list.tail)
        last = last.next;

    let newNode = {
        data: data,
        next: list.tail
    };
    last.next = newNode;
    list.size++;
}

3. removeNode(list, data)

리스트의 노드를 하나씩 돌면서 data가 일치하면 그 노드를 삭제하는 겁니다.
주의할 점은 그 노드 다음 노드를 이전의 노드가 가리키는 작업이 우선적으로 이루어져야한다는 겁니다.

//java

public void removeNode(List list, int data) {
    Node node = list.head;
    while (node.next != list.tail) {
        if (node.next.data == data) {
            Node delNode = node.next;
            node.next = delNode.next;
            delNode.next = null;
            list.size--;
            return;
        }
        node = node.next;
    }
    System.out.println("데이터를 찾지 못했습니다.");
}
//js

function removeNode(list, data) {
    let node = list.head;
    while (node.next !== list.tail) {
        if (node.next.data === data) {
            let delNode = node.next;
            node.next = delNode.next;
            delNode.next = null;
            list.size--;
            return;
        }
        node = node.next;
    }
    console.log("데이터를 찾지 못했습니다.");
}

4. searchNode(list, data)

삭제 연산보다 쉽습니다. list를 돌면서 data와 값이 일치하면 그 노드를 반환하면 되니까요.

//java

public void removeNode(List list, int data) {
    Node node = list.head;
    while (node.next != list.tail) {
        if (node.next.data == data) {
            Node delNode = node.next;
            node.next = delNode.next;
            delNode.next = null;
            list.size--;
            return;
        }
        node = node.next;
    }
    System.out.println("데이터를 찾지 못했습니다.");
}

//js

function removeNode(list, data) {
    let node = list.head;
    while (node.next !== list.tail) {
        if (node.next.data === data) {
            let delNode = node.next;
            node.next = delNode.next;
            delNode.next = null;
            list.size--;
            return;
        }
        node = node.next;
    }
    console.log("데이터를 찾지 못했습니다.");
}

5. printList(list)

이 함수 역시 정말 쉽습니다. search 연산과 별 다를 것이 없죠. 그냥 list돌면서 하나하나 출력해주기만 하면 됩니다.

//java

public void printList(List list) {
    Node node = list.head.next;
    while (node != list.tail) {
        System.out.println(node.data);
        node = node.next;
    }
}
//js

function printList(list) {
    let node = list.head.next;
    while (node !== list.tail) {
        console.log(node.data);
        node = node.next;
    }
}

마무리

여기있는 코드를 모두 이해할 필요는 없다고 생각한다. 하지만 해당 자료구조가 어떤 원리로 동작하는지를 알게된다면, 80%는 성공한 것이라고 생각한다.

연결리스트와 배열에 대한 정의와 차이점에 대한 질문에 대해서 답변을 할 수 있다면 GOOD!!!

질문에 대한 모범 답안

  • 연결 리스트 (Linked List):
    연결 리스트는 데이터 요소를 노드라는 개별적인 단위로 저장합니다.
    각 노드는 데이터와 다음 노드를 가리키는 포인터 (또는 링크)로 이루어져 있습니다.

  • 배열 (Array):
    배열은 동일한 데이터 타입의 요소를 연속적으로 저장하는 선형 자료구조입니다.
    인덱스를 사용하여 각 요소에 접근합니다.

  • 주요 차이점:

    • 메모리 구조: 연결 리스트는 노드들이 불연속적으로 메모리에 저장되며, 포인터로 연결되어 있습니다. 배열은 연속적으로 메모리에 저장됩니다.
    • 크기 조정: 연결 리스트는 동적으로 크기를 조정할 수 있습니다. 배열은 크기가 고정되어 있어 변경하기 위해서는 새로운 배열을 생성하고 요소를 복사해야 합니다.
    • 삽입 및 삭제: 연결 리스트는 삽입과 삭제가 상대적으로 간단하며, 해당 위치에 대한 요소의 이동이 필요하지 않습니다. 배열은 삽입과 삭제에 따라 요소의 이동이 필요할 수 있습니다.
    • 검색: 배열은 인덱스를 통해 빠르게 요소에 접근할 수 있어 검색이 빠릅니다. 연결 리스트는 처음부터 순차적으로 접근해야 하므로 검색 시간이 느립니다.
profile
hanseungjune
필요하다면 공부하는 개발자, 한승준
이전 포스트

[CS]_DataBase의 기본

다음 포스트

[자료구조]_DFS/BFS

0개의 댓글