3. 리스트 - 연결리스트(Linked List)

1. Linked List 개념

Node는 데이터 필드와 다음 Node를 가르키는 포인터 필드로 구성되어 있다.

가장 앞에 위치한 Node = Head

가장 뒤에 위치한 Node = Tail 이며 Tail은 가르킬 Node가 없으므로 Null을 가르킨다.

데이터 검색 시 인덱스 기반이 아니라 Node들의 Pointer를 통해 검색해 들어가야하므로,

검색의 시간 복잡도가 데이터의 개수와 같은 O(n)이다.

 

데이터 추가 시 Tail에 추가 Node를 넣어주므로 시간 복잡도가 역시 O(n)이다.

 

데이터 삽입 시 데이터를 배열 리스트처럼 뒤로 미뤄줄 필요는 없고, 포인터를 통해 연결해주면 된다.

다만, 데이터 삽입 될 곳을 찾아가는 과정 때문에 시간 복잡도가 역시 O(n)이다.

또한, Head에 앞쪽으로 데이터 삽입 시에는 간단하게 포인터만 지정해주면 된다.

 

데이터 삭제 시 삭제하고자 하는 데이터를 찾아가서 포인터만 바꿔주면 된다.

참조하지도 참조 되지도 않는 삭제할 Node는 나중에 가비지 컬렉터가 수거해가게 된다. 

이 때, 삭제할 데이터를 찾아가는 과정 때문에 시간 복잡도는 O(n)이 된다.

 

장점 : 배열의 복사나 재할당 없이 데이터 추가 가능 / 유연한 공간(자기가 쓰는 공간 만큼만 사이즈를 차지)

단점 : 데이터 접근(검색)에 대한 시간이 늘어남 O(n)

---

2. Linked List 구현 (JAVA)

Head를 더미 Node(데이터 X)로 만들어 두고 구현하면 코드가 더 간결해 진다.

Node class를 먼저 만들어 주고 시작.

 

package list;

public class MyLinkedList<T> implements IList<T> {

    private int size;                       // 데이터 사이즈 변수
    private Node head;                      // 헤드 노드

    public MyLinkedList() {                 // 생성자
        this.size = 0;
        this.head = new Node(null);     // 헤드 노드를 더미노드로 초기화
    }

    @Override
    public void add(T t) {                  // LinkedList 끝에 데이터를 넣어주는 동작
        Node current = this.head;          
        while (current.next != null) {       // 포인터가 null Tail 노드까지 찾아들어가기
            current = current.next;
        }
        Node n = new Node(t);               // 새로운 노드 생성 후 데이터 넣어주기
        current.next = n;                   // 기존 Tail Node의 포인터를 새로운 삽입한 노드로 
        this.size++;                        // 데이터 사이즈 변수 +1
    }

    @Override
    public void insert(int index, T t) {            // 지정한 인덱스에 데이터 노드를 삽입하는 동작
        if (index > this.size || index < 0) {       // 인덱스 오류 처리
            throw new IndexOutOfBoundsException();
        }

        Node prev = this.head;                      // 탐색하고 있는 노드 지정
        Node current = prev.next;

        int i = 0;                                  // 인덱스까지 노드 탐색
        while (i++ < index) {
            prev = prev.next;
            current = current.next;
        }

        Node newNode = new Node(t, current);        // prev와 current 사이에 새로운 노드 생성해서 current로 포인터 지정
        prev.next = newNode;                        // prev의 포인터를 새로만든 Node로 지정
        this.size++;                                // 데이터 사이즈 변수 +1
    }

    @Override
    public void clear() {                   // LinkedList안에 데이터를 모두 비워준다
        this.size = 0;
        this.head.next = null;              // Head의 포인트를 Null로 바꿔버린다.
    }

    @Override
    public boolean delete(T t) {            // 데이터(t)가 들어있는 Node를 삭제
        Node prev = this.head;               // 탐색 노드 지정
        Node current = prev.next;
        while (current != null) {            // Tail까지 노드 탐색을 하다가
            if (current.data.equals(t)) {    // Node의 데이터가 일치하면
                prev.next = current.next;    // 삭제할 노드 전에 위치한 노드의 포인터를 삭제할 노드가 가르키는 노드로
                current.next = null;         // 삭제할 노드의 포인터는 null 바꿔준다
                this.size--;                 // 데이터 크기 -1
                return true;
            }
            prev = prev.next;
            current = current.next;
        }
        return false;
    }

    @Override
    public boolean deleteByIndex(int index) {       // 인덱스로 찾아가서 Node 삭제 동작
        if (index >= this.size || index < 0) {          // 인덱스 오류 처리
            throw new IndexOutOfBoundsException();
        }

        Node prev = this.head;                  // 인덱스까지 노드 찾아가기
        Node current = prev.next;
        int i = 0;
        while (i++ < index) {
            prev = prev.next;
            current = current.next;
        }

        prev.next = current.next;               // 포인터 변경으로 노드 삭제
        current.next = null;
        this.size--;
        return true;
    }

    @Override
    public T get(int index) {                       // 인덱스 기반으로 노드의 데이터를 가져오는 동작
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node current = this.head.next;              // 노드 current만 필요하다
        int i = 0;
        while (i++ < index) {
            current = current.next;
        }
        return current.data;                        // currenet data 반환
    }

    @Override
    public int indexOf(T t) {                       // 해당 데이터(t)가 있는 곳의 index 반환
        Node current = this.head.next;
        int index = 0;
        while (current != null) {
            if (current.data != null && current.data.equals(t)) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    @Override
    public boolean isEmpty() {                  //head의 포인트가 null이면 비어 있는 리스트가 됨
        return this.head.next == null;
    }

    @Override
    public boolean contains(T t) {              // 데이터가(t)가 리스트안에 있는 지 확인하는 동작
        Node current = this.head.next;
        while (current != null) {
            if (current.data != null && current.data.equals(t)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    @Override
    public int size() {                         // 바로 size를 반환
        return this.size;
    }

    private class Node {         // 가장 먼저 Node를 만들어 준다
        T data;                  // 데이터 변수
        Node next;               // 포인터 변수

        Node(T data) {          //Node 데이터만 초기화 해주는 생성자
            this.data = data;
        }

        Node(T data, Node next) { //Node 데이터 및 포인터 초기화 해주는 생성자
            this.data = data;
            this.next = next;
        }
    }
}

---

3. Linked List 구현 (Python)

class Node(object):

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next_node

    def set_next(self, new_next):
        self.next_node = new_next

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

    def insert(self, data):
        new_node = Node(data)
        new_node.set_next(self.head)
        self.head = new_node

    def size(self):
        current = self.head
        count = 0
        while current:
            count += 1
            current = current.get_next()
        return count
    
    def search(self, data):
        current = self.head
        found = False
        while current and found is False:
            if current.get_data() == data:
                found = True
            else:
                current = current.get_next()
        if current is None:
            raise ValueError("Data not in list")
        return current

    def delete(self, data):
        current = self.head
        previous = None
        found = False
        while current and found is False:
            if current.get_data() == data:
                found = True
            else:
                previous = current
                current = current.get_next()
        if current is None:
            raise ValueError("Data not in list")
        if previous is None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())