[linked list][leetcode] linked list 개념정리

simple linked list 구조

릿코드를 이용해 공부중인데 다시한번 제대로 짚고 넘어가볼려한다. linked list 는 array 와 다르게 순서적으로 저장되어있지않고 그사이 연결고리는 pointer들로 구성되어있다.  Array 의 단점으로는

1. 사이즈가 고정되어있다 
2. 중간에 삽입 및 제거할려면 큰 resource가 들어간다.  왜냐면 하나를 중간에 추가할려면 그 뒤 어레이값들을 다 옮겨야한다.

이해 반해 linked list를 사용한다면 사이즈가 고정되어있지않아 쉽게 중간에 제거하거나 값을 추가할수있다. 중간에 가위로 싹뚝 짤라서 pointer로 새로운 노드를 이어주면 되므로 하지만 linked list의 단점으로는 

1.    binary search로 할경우 첫 노드의 헤드부터 순서대로 찾게되므로 다른 방식의 서치가 효율적이다. 
2.  추가 메모리가 들어가는데 이는 포인터 공간과 값 공간이 추가되므로!

---

기본적인 함수들 

struct LinkedListNode {
    int val;
    LinkedListNode *next;
    LinkedListNode(int val): val (val), next(nullptr) {}
};

int main() {
    LinkedListNode* one = new LinkedListNode(1);
    LinkedListNode* two = new LinkedListNode(2);
    LinkedListNode* three = new LinkedListNode(3);
    one->next = two;
    two->next = three;
    LinkedListNode* head = one;
    
    cout << head->val << endl;
    cout << head->next->val << endl;
    cout << head->next->next->val << endl;
}

                                                                 < struct 를 사용한 기초 linked list 구조>

struct라는건 자주 사용하고자하는 member variable들을 사용자가 임의로 만들어주는것으로 function과 대표적인 차이점은 사용목적에 있는데 struct는 임의 데이터 타입들을 만들어 데이터 구조들을 나타낼때쓰고 function은 코드 블록을 가지며 특정 테스크를 수행하고자 존재하는 문법. (위 코드 블록을 내재화시키며 이해)

 

또다른 예로는 

int getSum(ListNode* head) {
    int ans = 0;
    while (head != nullptr) {
        ans += head->val;
        head = head->next;
    }

    return ans;
}

                                                                            < linked list를 이용한 총합 함수>

 

linked list 종류 

1. Simple Linked List

오직 한방으로 traverse (순회) 할 수 없다. 마지막 노드의 포인터는 NULL

 

2. Doubly Linked List

양방향으로 Traverse 할수있다 <-> 게 포인터가 이어져있음 

 

3. Circular Linked List

simple linked 에 마지막 노드의 포인터가 처음 노드를 가리키고있어 원형 형태의 linked list 모양

 

4. Doubly Circular Linked List

Double linked에 circular 방식을 합친것으로 한 노드가 다음 노드의 주소와 그 이전 노드의 주소를 가지고있어 왔다갔다할 수 있는것. 

struct ListNode {
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode(int val) : val(val), next(nullptr), prev(nullptr) {}
};

// Let node be the node at position i
void addNode(ListNode* node, ListNode* nodeToAdd) {
    ListNode* prevNode = node->prev;
    nodeToAdd->next = node;
    nodeToAdd->prev = prevNode;
    prevNode->next = nodeToAdd;
    node->prev = nodeToAdd;
}

void deleteNode(ListNode* node) {
    ListNode* prevNode = node->prev;
    ListNode* nextNode = node->next;
    prevNode->next = nextNode;
    nextNode->prev = prevNode;
}

                                                         < linked list를 이용한 첨삭>

 

 

 

5. Header linked List

header node가 리스트 첫번쨰에 속해있는 특별한 linked list라고함.

---

기본 함수들

• Deletion , Insertion , Search Display  이것들은 차근차근 하나 씩 살펴볼 예정

---

traversal of a linked list 예제

// traversal of a linked list
 
#include <bits/stdc++.h>
using namespace std;
 
class Node { // Node라는게 c++ 기본함수가 아니라 우리가 직접 설정해줘야하는 개념인것
public:
    int data; // node 안에 값으로 들어간다
    Node* next; // 포인터를 지칭한다. 
};
 
// This function prints contents of linked list
// starting from the given node
void printList(Node* n)
{
    while (n != NULL) {  순회하면 display
        cout << n->data << " ";
        n = n->next;
    }
}
 
// Driver's code
int main()
{
    Node* head = NULL; // 각노드의 포인터 위치 선언 
    Node* second = NULL;
    Node* third = NULL;
 
    // allocate 3 nodes in the heap
    head = new Node(); // 각각 노드 선언 
    second = new Node();
    third = new Node();
 
    head->data = 1; // assign data in first node
    head->next = second; // Link first node with second
 
    second->data = 2; // assign data to second node
    second->next = third;
 
    third->data = 3; // assign data to third node
    third->next = NULL;
 
    // Function call
    printList(head);
 
    return 0;
}

---

중요한 time complexity 표시