(3) Linked List

Huisu·2023년 4월 8일
0

Data Structure

목록 보기
3/4
post-thumbnail

Linked List

Node

A Single Node

  • .info: 실제 사용자의 데이터
  • .next: 다음 노드를 가리키는 포인터
  • node: 데이터 구조 중 한 요소
  • 특정 노드 관점에서 보면 자신의 뒷 요소밖에 모름
  • 사용자가 변수를 선언하는 시점에도 몇 개가 필요한지 모를 때 사용
  • 새 요소를 만들 때마다 heap 공간에 메모리를 동적으로 할당받음
    • delete 메소드를 통해 garbage 데이터 처리 필요

Destructor

  • 노드를 요소로 갖는 Local Variable의 topPtr에는 첫 노드의 주소 저장
  • 함수가 종료되면 Local variable 삭제
  • 삭제된 Local Variable의 top Ptr가 가리키던 노드들은 Garbage
  • Local Variable 삭제 전에 노드 메모리 해제가 필요함

Unsorted List

Application Level

  • Transformer
    • MakeEmpty
    • InsertItem
    • DeleteItem
  • Observe+
    • IsFull
    • LengthIs
    • RetriveItem
  • Iterators
    • ResetList
    • GetNextItem

Insert Method

  • 새 아이템을 가르킬 location pointer 생성 https://velog.velcdn.com/images/morion002/post/565f591b-2066-4df3-87b5-e60195dccd71/1.jpg
  • location에 동적 메모리를 할당해 새 아이템이 들어갈 장소 마련 https://velog.velcdn.com/images/morion002/post/34c6cd46-3cf5-4a9b-b0b7-7bcf6999322c/2.jpg
  • location에 새 아이템 넣기 https://velog.velcdn.com/images/morion002/post/ba9c38b2-de13-4052-ad5e-6f40ced7c1da/3.jpg
  • 새 아이템의 .next 가 현재 list의 끝 노드를 가리키도록 설정 https://velog.velcdn.com/images/morion002/post/3f981eb3-fe2d-4044-b44d-a19db9dfc253/4.jpg
  • 현재 list의 끝은 새 아이템까지 추가된 리스트를 가리키도록 설정 https://velog.velcdn.com/images/morion002/post/295fc799-6089-4c7a-be3f-377ec86163f0/5.jpg

DeleteItem Method

  • 리스트를 순회하면서 삭제할 아이템을 찾는 location 생성한 뒤 리스트의 맨 끝부터 시작 https://velog.velcdn.com/images/morion002/post/712eae23-f512-432a-9dcf-6fb13d10919d/1.jpg
  • 삭제할 아이템을 찾으면 그 아이템을 가리킬 tempLocation pointer 설정 https://velog.velcdn.com/images/morion002/post/a7d2ea94-9894-467e-95fe-6ad9c0fa9bc0/2.jpg
  • 만약 아이템이 처음에 있을 때 https://velog.velcdn.com/images/morion002/post/1c6b2431-b14b-4b5d-9b2c-f3abb6179a4f/3.jpg
    • tempLocation이 삭제할 아이템인 location이 가리키는 노드를 가리키도록 설정 https://velog.velcdn.com/images/morion002/post/67c78926-d207-41d5-9fbf-375dc9f666d7/4.jpg
    • 리스트의 끝인 listData는 곧 삭제될 아이템의 .next인 다음 노드를 가리키도록 설정
  • 만약 아이템이 중간에 있을 때
    • 순회하는 포인터인 location이 나타내는 노드의 다음 노드가 삭제할 아이템일 때까지 순회 https://velog.velcdn.com/images/morion002/post/46226870-79b2-457e-aa14-f0d4573d26bf/6.jpg
    • 아이템을 찾았다면 삭제할 노드를 나타내는 tempLocation이 location의 다음 노드를 가리키도록 설정 https://velog.velcdn.com/images/morion002/post/fab47ab5-39e9-43c8-9978-702dadec63ad/7.jpg
    • listData 노드의 next가 삭제할 노드의 다음인 tempLocation이 나타내는 노드의 다음을 가리키도록 설정 https://velog.velcdn.com/images/morion002/post/5a440298-8078-44a6-9fd5-c4374ee73cd0/8.jpg
  • 아이템을 모두 찾은 뒤 tempLocation 동적 할당 메모리 해제 https://velog.velcdn.com/images/morion002/post/d271bb30-ecfd-4f8f-8c52-d14837363388/9.jpg

Unsorted Linked List with C++

  • UnsortedLinkedlist.cpp
    #include <cstddef>
    #include <new>
    
    template <class ItemType>
    struct NodeType;
    
    template<class ItemType>
    class UnsortedType {
    public:
    	UnsortedType();
    	~UnsortedType();
    	void MakeEmpty();
    	void InsertItem(ItemType item);
    	void DeleteItem(ItemType item);
    	bool IsFull();
    	int LengthIs();
    	void RetrieveItem(ItemType& item, bool& found);
    	void ResetList();
    	void GetNextItem(ItemType& item);
    private:
    	int length; // list 길이 세는 변수
    	NodeType<ItemType>* listData; // list를 나타내는 pointer
    	NodeType<ItemType>* currentPos;
    };
    
    // Node에 info와 next 있도록 정의
    template<class ItemType>
    struct NodeType {
    	ItemType info;
    	NodeType<ItemType>* next;
    };
    
    template<class ItemType>
    UnsortedType<ItemType>::UnsortedType() {
    	length = 0;
    	listData = NULL;
    }
    
    template<class ItemType>
    UnsortedType<ItemType>::~UnsortedType() {
    	MakeEmpty();
    }
    
    template<class ItemType>
    void UnsortedType<ItemType>::MakeEmpty() {
    	NodeType<ItemType>* tempPtr;
    
    	while (listData != NULL) {
    		tempPtr = listData;
    		listData = listData->next;
    		delete tempPtr;
    	}
    	length = 0;
    }
    
    template<class ItemType>
    bool UnsortedType<ItemType>::IsFull() {
    	NodeType<ItemType>* location;
    	try {
    		location = new NodeType<ItemType>;
    		delete location;
    		return false;
    	}
    	catch (std::bad_alloc exception) {
    		return true;
    	}
    }
    
    template<class ItemType>
    int UnsortedType<ItemType>::LengthIs() {
    	return length;
    }
    
    template<class ItemType>
    void UnsortedType<ItemType>::InsertItem(ItemType item) {
    	NodeType<ItemType>* location;
    	location = new NodeType<ItemType>;
    	location->info = item;
    	location->next = listData;
    	listData = location;
    	length++;
    }
    
    template<class ItemType>
    void UnsortedType<ItemType>::DeleteItem(ItemType item) {
    	NodeType<ItemType>* location;
    	NodeType<ItemType>* tempLocation;
    	location = listData;
    	if (location->info == item) { // 처음에 item 존재
    		tempLocation = location;
    		listData = location->next;
    	}
    	else {// 중간에 item 존재
    		while ((location->next)->info != item)
    			location = location->next;
    		tempLocation = location->next;
    		location->next = (location->next)->next;
    	}
    	delete tempLocation;
    	length--;
    }
    
    template<class ItemType>
    void UnsortedType<ItemType>::ResetList() {
    	currentPos = NULL;
    }
    
    template<class ItemType>
    void UnsortedType<ItemType>::GetNextItem(ItemType& item) {
    	if (currentPos == NULL) {
    		currentPos = listData;
    	}
    	else {
    		currentPos = currentPos->next;
    	}
    	item = currentPos->info;
    }
    
    template<class ItemType>
    void UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool& found) {
    	NodeType<ItemType>* location = listData;
    	bool moreToSearch = (location != NULL);
    	found = false;
    	while (moreToSearch && !found) {
    		if (location->info == item) {
    			found = true;
    			item = location->info;
    		}
    		else {
    			location = location->next;
    			moreToSearch = (location != NULL);
    		}
    	}
    }
  • Big O Comparision
    OperationArray ImplementaionLinked-list Implementation
    ConstructorO(1)O(1)
    MakeEmptyO(1)O(N)
    InsertItemO(1)O(1)
    DeleteItemO(N)O(N)
    IsFullO(1)O(1)
    LengthIsO(1)O(1)
    RetrieveItemO(N)O(N)
    ResetListO(1)O(1)
    GetNextItemO(1)O(1)
    DestructorO(1)O(N)

Unsorted Linked List with JAVA

public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedList {
    Node head;

    public LinkedList() {
        head = null;
    }

    // 노드를 리스트의 맨 앞에 추가하는 메소드
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 노드를 리스트의 맨 끝에 추가하는 메소드
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 리스트에서 노드를 삭제하는 메소드
    public void delete(int data) {
        if (head == null) {
            return;
        }
        if (head.data == data) {
            head = head.next;
            return;
        }
        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 리스트를 출력하는 메소드
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

Unsorted Linked List with Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    # 노드를 리스트의 맨 앞에 추가하는 메소드
    def add_first(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # 노드를 리스트의 맨 끝에 추가하는 메소드
    def add_last(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

    # 리스트에서 노드를 삭제하는 메소드
    def delete(self, data):
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    # 리스트를 출력하는 메소드
    def print_list(self):
        current = self.head
        while current is not None:
            print(current.data, end=' ')
            current = current.next

Sorted List

Application Level

  • Transformer
    • MakeEmpty
    • InsertItem
    • DeleteItem
  • Observe+
    • IsFull
    • LengthIs
    • RetriveItem
  • Iterators
    • ResetList
    • GetNextItem

Insert Method

  • 새 요소를 넣어야 할 위치 찾기
  • 새 요소 뒷 순서를 하나씩 뒷 index로 밀어서 자리 생성
  • 빈 공간에 요소 삽입
  • 길이 증가
  • location Pointer 하나만 사용하는 경우
    • 각 노드는 자신의 다음 노드만 알고 있음
    • 새로운 item을 추가하면 item 전에 오는 노드의 next가 item을 가리킬 수 있도록 해야 함
    • 따라서 location이 아닌 (location->next)->info로 검색
    • 만약 item이 마지막에 들어가는 경우 참조 오류 발생 https://velog.velcdn.com/images%2Fmorion002%2Fpost%2F346d108e-d9b5-4729-956a-ab14a980d049%2F1.jpg
    • location->next 는 NULL 값이라 item 추가 불가능
    • item이 들어가기 바로 전 위치를 가리키는 preLoc Pointer 추가
  • 순회하는 pointer location, 새로 추가할 노드 pointer인 newNode, item의 위치를 찾았는지 말해 주는 moreToSearch, item이 들어가는 바로 직전 위치를 말해 주는 preLoc pointer 생성 https://velog.velcdn.com/images/morion002/post/4802f5c5-b9a5-49b1-99e0-d4dd675754f1/2.jpg
  • 순회하는 location을 시작점인 listData에 두고 moreToSearch라면 계속 방문하며 아이템을 넣을 위치 찾기 https://velog.velcdn.com/images/morion002/post/463f8985-d42f-4ae7-ae4e-7c9be3fdfc2c/3.jpg
  • 새로 넣을 노드를 나타내는 newNode에 노드 하나 동적 할당 https://velog.velcdn.com/images/morion002/post/b1056cbf-418a-4cf5-84df-f0bd1eba6629/1.jpg
  • 노드 정보 넣어 주기 https://velog.velcdn.com/images/morion002/post/255acf87-8d35-413b-aed2-a3cb87047935/2.jpg
  • 아이템 넣을 위치 찾기
    • 아이템이 location의 데이터보다 작은 경우
      • preLoc을 location으로 하나 이동 https://velog.velcdn.com/images/morion002/post/eb50c841-0ba9-4462-b106-41ca8170d55a/4.jpg
      • location을 location의 next가 나타내는 노드로 하나 이동 https://velog.velcdn.com/images/morion002/post/73bb9147-950c-49f5-bcb9-c1c86e06b25a/5.jpg
      • moreToSearch가 location이 NULL인지 검사 (맨 끝에 들어가는 경우를 대비해)
    • 아이템이 location의 데이터보다 큰 경우
      • moreToSearch False 만들기
  • 아이템 넣을 위치를 찾았을 때
    • 아이템이 첫 순서에 들어가는 경우
      • 새 노드의 next가 현재까지의 리스트를 가리키게 함 https://velog.velcdn.com/images/morion002/post/c0a7b76d-d67f-4c7d-a42b-90ec7069f219/3.jpg
      • 리스트의 끝인 listData를 새로운 노드인 newNode로 바꿔 줌 https://velog.velcdn.com/images/morion002/post/c10cd122-4f66-4403-be2d-6d3603984ad0/5.jpg
    • 아이템이 중간 위치에 들어가는 경우
      • location과 preLoc 사이에 newNode가 존재해야 함
      • newNode의 다음 아이템을 location으로 지정 https://velog.velcdn.com/images/morion002/post/c10cd122-4f66-4403-be2d-6d3603984ad0/5.jpg
      • preLoc의 다음 아이템을 newNode로 지정 https://velog.velcdn.com/images/morion002/post/ea3a6748-0c44-4cb4-8871-383fb1fa98bb/6.jpg

Delete Item

  • 리스트를 순회하면서 삭제할 아이템을 찾는 location 생성한 뒤 리스트의 맨 끝부터 시작 https://velog.velcdn.com/images/morion002/post/712eae23-f512-432a-9dcf-6fb13d10919d/1.jpg
  • 삭제할 아이템을 찾으면 그 아이템을 가리킬 tempLocation pointer 설정 https://velog.velcdn.com/images/morion002/post/a7d2ea94-9894-467e-95fe-6ad9c0fa9bc0/2.jpg
  • 만약 아이템이 처음에 있을 때 https://velog.velcdn.com/images/morion002/post/1c6b2431-b14b-4b5d-9b2c-f3abb6179a4f/3.jpg
    • tempLocation이 삭제할 아이템인 location이 가리키는 노드를 가리키도록 설정 https://velog.velcdn.com/images/morion002/post/67c78926-d207-41d5-9fbf-375dc9f666d7/4.jpg
    • 리스트의 끝인 listData는 곧 삭제될 아이템의 .next인 다음 노드를 가리키도록 설정
  • 만약 아이템이 중간에 있을 때
    • 순회하는 포인터인 location이 나타내는 노드의 다음 노드가 삭제할 아이템일 때까지 순회 https://velog.velcdn.com/images/morion002/post/46226870-79b2-457e-aa14-f0d4573d26bf/6.jpg
    • 아이템을 찾았다면 삭제할 노드를 나타내는 tempLocation이 location의 다음 노드를 가리키도록 설정 https://velog.velcdn.com/images/morion002/post/fab47ab5-39e9-43c8-9978-702dadec63ad/7.jpg
    • listData 노드의 next가 삭제할 노드의 다음인 tempLocation이 나타내는 노드의 다음을 가리키도록 설정 https://velog.velcdn.com/images/morion002/post/5a440298-8078-44a6-9fd5-c4374ee73cd0/8.jpg
  • 아이템을 모두 찾은 뒤 tempLocation 동적 할당 메모리 해제 https://velog.velcdn.com/images/morion002/post/d271bb30-ecfd-4f8f-8c52-d14837363388/9.jpg

Sorted Linked List with C++

  • SortedLinkedList.cpp
    #include <cstddef>
    #include <new>
    #include "ItemType.h"
    #define MAX_ITEMS 100
    
    template<class ItemType>
    class SortedType {
    public:
    	SortedType();
    	~SortedType();
    	void MakeEmpty();
    	void InsertItem(ItemType item);
    	void DeleteItem(ItemType item);
    	bool IsFull();
    	int LengthIs();
    	void RetrieveItem(ItemType& item, bool& found);
    	void ResetList();
    	void GetNextItem(ItemType& item);
    private:
    	int length;
    	NodeType<ItemType>* listData;
    	NodeType<ItemType>* currentPos;
    };
    
    template<class ItemType>
    struct NodeType {
    	ItemType info;
    	ItemType* next;
    };
    
    template<class ItemType>
    SortedType<ItemType>::SortedType() {
    	length = 0;
    	listData = NULL;
    }
    
    template<class ItemType>
    SortedType<ItemType>::~SortedType() {
    	MakeEmpty();
    }
    
    template<class ItemType>
    void SortedType<ItemType>::MakeEmpty() {
    	NodeType<ItemType>* tempPtr;
    	while (listData != NULL) {
    		tempPtr = listData;
    		listData = listData->next;
    		delete tempPtr;
    	}
    	length = 0;
    }
    
    template<class ItemType>
    bool SortedType<ItemType>::IsFull() {
    	NodeType<ItemType>* location;
    	try {
    		location = new NodeType<ItemType>;
    		delete location;
    		return false;
    	}
    	catch (std::bad_alloc exception) {
    		return true;
    	}
    }
    
    template<class ItemType>
    int SortedType<ItemType>::LengthIs() {
    	return length;
    }
    
    template<class ItemType>
    void SortedType<ItemType>::InsertItem(ItemType item) {
    	NodeType<ItemType>* location;
    	NodeType<ItemType>* preLoc;
    	NodeType<ItemType>* newNode;
    	location = listData;
    	preLoc = NULL;
    	bool moreToSearch = (location != NULL);
    	while (mroeToSearch) {
    		if (location->info < item) {
    			preLoc = location;
    			location = location->next;
    			moreToSearch = (location != NULL);
    		}
    		else
    			moreToSearch = false;
    	}
    	newNode = new NodeType<ItemType>;
    	newNode->info = item;
    	if (preLoc == NULL) {
    		newNode->next = location;
    		listData = newNode;
    	}
    	else {
    		newNode->next = location;
    		preLoc->next = newNode;
    	}
    	length++;
    }
    
    template<class ItemType>
    void SortedType<ItemType>::DeleteItem(ItemType item) {
    	NodeType<ItemType>* location;
    	NodeType<ItemType>* tempLocation;
    	location = listData;
    	if (location->info == item) { // 처음에 item 존재
    		tempLocaton = location;
    		listData = location->nextl
    	}
    	else {// 중간에 item 존재
    		while ((location->next)->infp != item)
    			locaiton = location->next;
    		tempLocation = location->next;
    		location->next = (location->next)->next;
    	}
    	delete tempLocation;
    	length--;
    }
    
    template<class ItemType>
    void SortedType<ItemType>::ResetList() {
    	currentPos = NULL;
    }
    
    template<class ItemType>
    void SortedType<ItemType>::GetNextItem(ItemType& item) {
    	if (currentPos == NULL) {
    		currentPos = listData;
    	}
    	else {
    		currentPos = currentPos->next;
    	}
    	item = currentPos->info;
    }
    
    template<class ItemType>
    void SortedType<ItemType>::RetrieveItem(ItemType& item, bool& found) {
    	NodeType<ItemType>* location = listData;
    	bool moreToSearch = (location != NULL);
    	found = false;
    	while (moreToSearch && !found) {
    		if (location->info == item) {
    			found = true;
    			item = location->info;
    		}
    		else {
    			location = location->next;
    			moreToSearch = (location != NULL);
    		}
    	}
    }
  • Big O Comparison
    OperationArray ImplementaionLinked-list Implementation
    ConstructorO(1)O(1)
    MakeEmptyO(1)O(N)
    InsertItemO(1)O(1)
    DeleteItemO(N)O(N)
    IsFullO(1)O(1)
    LengthIsO(1)O(1)
    RetrieveItemO(N)O(N)
    ResetListO(1)O(1)
    GetNextItemO(1)O(1)
    DestructorO(1)O(N)

Sorted Linked List with JAVA

public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SortedLinkedList {
    Node head;

    public SortedLinkedList() {
        head = null;
    }

    // 노드를 정렬된 위치에 삽입하는 메소드
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null || data < head.data) {
            newNode.next = head;
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null && current.next.data < data) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
    }

    // 리스트에서 노드를 삭제하는 메소드
    public void delete(int data) {
        if (head == null) {
            return;
        }
        if (head.data == data) {
            head = head.next;
            return;
        }
        Node current = head;
        while (current.next != null && current.next.data != data) {
            current = current.next;
        }
        if (current.next != null) {
            current.next = current.next.next;
        }
    }

    // 리스트를 출력하는 메소드
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

Sorted Linked List with Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SortedLinkedList:
    def __init__(self):
        self.head = None

    # 노드를 정렬된 위치에 삽입하는 메소드
    def insert(self, data):
        new_node = Node(data)
        if self.head is None or data < self.head.data:
            new_node.next = self.head
            self.head = new_node
            return
        current = self.head
        while current.next is not None and current.next.data < data:
            current = current.next
        new_node.next = current.next
        current.next = new_node

    # 리스트에서 노드를 삭제하는 메소드
    def delete(self, data):
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next is not None and current.next.data != data:
            current = current.next
        if current.next is not None:
            current.next = current.next.next

    # 리스트를 출력하는 메소드
    def print_list(self):
        current = self.head
        while current is not None:
            print(current.data, end=' ')
            current = current.next

Array VS Linked List

Memory Comparision

  • Array-based Implimentation
    • item 하나가 80bytes라고 가정하면 100개의 item으로 이루어진 배열은 8000bytes
    • Reserved cell 80 bytes
    • front와 rear Pointer은 각각 2bytes씩 차지해서 총 4bytes
    • 8084 bytes
  • Linked-list Implimentation
    • Node의 info는 80bytes next Pointer는 4bytes
    • Node 하나 당 84bytes
  • Array는 항상 일정한 수의 메모리 사용
  • Linked-list는 item의 수가 많아질수록 많은 메모리 사용
  • 하나의 item이 차지하는 메모리 크기가 클수록 Linked-list가 유리

0개의 댓글