알고리즘/Java 기초

자바 자료구조2 -이중 연결리스트(LinkedList)

1. 단일 연결리스트의 한계

 

단일 연결리스트는 결국 한방향으로만 이동할 수 있다는 한계점이 있어서 다른 방향으로 탐색하는 것이 불가능하다

 

때로는 다른 방향으로도 탐색하고 싶을 수 있는데 이런 문제를 해결하기 위해 next를 확장해서

 

특정 노드의 뒷 노드만 이어주는 것이 아니라, 앞 노드까지 이어질 수 있도록 한다.

 

 

 

2. 이중 연결리스트

 

단순히 단일 연결리스트에 새로운 노드로 prev를 추가한 것 뿐이다.

 

이중 연결리스트 역시 단일 연결리스트와 마찬가지로 삽입, 삭제, 탐색이 모두 가능하다.

 

탐색은 방향성이 양쪽에서 있다고는 하지만 어쨌든 일일이 확인해야하므로 O(N)

 

하지만 삽입, 삭제의 경우 해당하는 위치를 알고있다면 그냥 선을 끊고 연결해주는 작업만 하면 되므로 O(1)

 

이때 이중연결리스트는 한방향이 아닌 양방향으로 적절하게 바꿔줘야한다.

 

 

3. 간단하게 구현해보기

 

파이썬으로 간단하게 구현해볼까?

 

자바로 해야하는데;;

 

Node 클래스에는 next 뿐만 아니라 prev도 추가해준다

 

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

 

head 앞에 새로운 노드를 추가할려면..?

 

새로운 노드를 먼저 만든다

 

새로운 노드의 next를 현재 연결리스트의 head로 변경

 

새로운 노드의 prev는..? None이겠지

 

현재 연결리스트의 head의 prev는? 새로운 노드가 될 것이고

 

현재 연결리스트의 head는 새로운 노드로 변경시켜줘야겠지

 

 

class DLL():
    
    def __init__(self,head,tail):
        
        self.head = head
        self.tail = tail
    
    def insert_front(self,num):
        
        new_node = Node(num)
        
        new_node.next = self.head
        
        new_node.prev = None
        
        self.head.prev = new_node
        
        self.head = new_node

 

 

다음 tail 뒤에 새로운 노드를 추가할려면 어떻게 해야할까?

 

새로운 노드를 먼저 만들고

 

새로운 노드는 tail이 될거니까 새로운 노드의 next는 None으로 없겠지

 

새로운 노드의 prev는? 현재 연결리스트의 tail이 될거고

 

현재 연결리스트의 tail의 next는 새로운 노드가 될거고

 

이제 연결리스트의 tail을 새로운 노드로 바꿔준다

 

 

class DLL():
    
    def __init__(self,head,tail):
        
        self.head = head
        self.tail = tail
    
    #head 앞에 노드 추가
    def insert_front(self,num):
        
        new_node = Node(num)
        
        new_node.next = self.head
        
        new_node.prev = None
        
        self.head.prev = new_node
        
        self.head = new_node
    
    #tail 뒤에 노드 추가
    def insert_end(self,num):
        
        new_node = Node(num)
        
        new_node.next = None
        
        new_node.prev = self.tail
        
        self.tail.next = new_node
        
        self.tail = new_node

 

head를 제거할려면 어떻게 해야할까..?

 

현재 head의 next의 prev를 None으로 해서 제거하고..

 

현재 head를 현재 head의 next로 바꾼다

 

class DLL():
    
    def __init__(self,head,tail):
        
        self.head = head
        self.tail = tail
    
    #head 앞에 노드 추가
    def insert_front(self,num):
        
        new_node = Node(num)
        
        new_node.next = self.head
        
        new_node.prev = None
        
        self.head.prev = new_node
        
        self.head = new_node
    
    #tail 뒤에 노드 추가
    def insert_end(self,num):
        
        new_node = Node(num)
        
        new_node.next = None
        
        new_node.prev = self.tail
        
        self.tail.next = new_node
        
        self.tail = new_node
    
    #head를 제거하고 head의 값을 반환
    
    def delete_front(self):
        
        result = self.head.data
        
        self.head.next.prev = None
        self.head = self.head.next
        
        return result

 

tail을 제거할려고 하면 어떻게 해야할까?

 

tail의 prev의 next를 None으로 바꿔서 제거해주고

 

현재 tail을 tail의 prev로 변경시켜주면 될 것이다

 

 

class DLL():
    
    def __init__(self,head,tail):
        
        self.head = head
        self.tail = tail
    
    #head 앞에 노드 추가
    def insert_front(self,num):
        
        new_node = Node(num)
        
        new_node.next = self.head
        
        new_node.prev = None
        
        self.head.prev = new_node
        
        self.head = new_node
    
    #tail 뒤에 노드 추가
    def insert_end(self,num):
        
        new_node = Node(num)
        
        new_node.next = None
        
        new_node.prev = self.tail
        
        self.tail.next = new_node
        
        self.tail = new_node
    
    #head를 제거하고 head의 값을 반환
    
    def delete_front(self):
        
        result = self.head.data
        
        self.head.next.prev = None
        self.head = self.head.next
        
        return result
    
    #tail을 제거하고 tail의 값을 반환
    
    def delete_end(self):
        
        result = self.tail.data
        
        self.tail.prev.next = None
        self.tail = self.tail.prev
        
        return result

 

 

개념을 대충 알았으니까.. 머리속으로 생각해보면서.. head를 제거하면.. prev, next 연결은 어떻게 해야하는지.. 생각해보면서

 

tail을 제거하면 연결은 어떻게 하는지.. 노드를 삽입하면 연결을 어떻게 바꿔줘야할지.. 외우지 않아도 그런거 생각하면 구현 쉽겠는데

 

 

3. LinkedList

 

자바에서는 이중연결리스트를 구현해놓은 LinkedList라는 클래스를 제공한다

 

import java.util.LinkedList;

 

LinkedList<(type)> (name) = new LinkedList<>(); 형태의 선언으로 사용가능하다.

 

여기서 (type)은 원소가 들어갈 데이터 타입으로 reference type이어야 한다고 한다

 

정수형 자료를 관리하는 LinkedList는..

 

import java.util.LinkedList;

public class Main {
    public static void main(String[] args){
        LinkedList<Integer> list = new LinkedList<>();
    }
}

 

4. 핵심 메소드

 

이중연결리스트를 이용할때 자주 사용하는 핵심 메소드는 다음과 같다

 

1) addFirst(E)

 

맨 앞에 데이터 E를 추가

 

2) addLast(E)

 

맨 뒤에 데이터 E를 추가

 

3) pollFirst()

 

맨 앞에 있는 데이터를 반환하고, 해당 데이터를 이중연결리스트에서 삭제시킨다

 

4) pollLast()

 

맨 뒤에 있는 데이터를 반환하고, 해당 데이터를 이중연결리스트에서 삭제시킨다

 

5) size()

 

현재 이중연결리스트에 들어있는 데이터의 수를 반환

 

6) isEmpty()

 

현재 이중연결리스트가 비어있다면 true, 아니라면 false를 반환

 

7) peekFirst()

 

이중연결리스트의 맨 앞에 있는 데이터를 반환

 

8) peekLast()

 

이중연결리스트의 맨 뒤에 있는 데이터를 반환

 

package array;

import java.util.LinkedList;

public class Main3 {
	
	public static void main(String[] args) {
		
		//정수를 관리할 이중연결리스트
		LinkedList<Integer> list = new LinkedList<>();
		
		//맨 앞에 3을 추가
		list.addFirst(3);
		//맨 앞에 5를 추가
		list.addFirst(5);
		
		// 맨 앞의 수를 출력
		System.out.println("맨 앞:" + list.peekFirst());
		
		// 맨 뒤의 수를 출력
		System.out.println("맨 뒤:" + list.peekLast());
		
		// 맨 뒤에 9를 추가
		list.addLast(9);
		
		// 맨 뒤의 수를 출력
		System.out.println("맨 뒤:" + list.peekLast());
		
		// 맨 앞의 숫자를 출력
		list.pollFirst();
		
		//맨 앞에 적힌 숫자 3을 출력
		System.out.println("맨 앞:" + list.peekFirst());
		
		// 원소의 개수를 출력
		System.out.println("개수:" + list.size());
		
		
	}

}

맨 앞:5
맨 뒤:3
맨 뒤:9
맨 앞:3
개수:2

 

 

5. 연습문제

 

정수형 이중연결리스트를 이용해서 다음 연산을 수행하는 프로그램 작성

 

  1. push_front A: 정수 A를 연결 리스트의 앞에 넣습니다.
  2. push_back A: 정수 A를 연결 리스트의 뒤에 넣습니다.
  3. pop_front: 연결 리스트의 가장 앞에 있는 수를 빼고, 그 수를 출력합니다.
  4. pop_back: 연결 리스트의 가장 뒤에 있는 수를 빼고, 그 수를 출력합니다.
  5. size: 연결 리스트에 들어있는 정수의 개수를 출력합니다.
  6. empty: 연결 리스트가 비어있으면 1을, 아니면 0을 출력합니다.
  7. front: 연결 리스트의 가장 앞에 있는 정수를 출력합니다.
  8. back: 연결 리스트의 가장 뒤에 있는 정수를 출력합니다.

 

 

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        LinkedList<Integer> list = new LinkedList<>();

        int N = sc.nextInt();

        for(int i = 1; i <= N; i++){

            String q = sc.next();

            if(q.equals("push_front")) {

                int a = sc.nextInt();

                list.addFirst(a);

            } else if(q.equals("push_back")) {

                int a = sc.nextInt();

                list.addLast(a);

            } else if(q.equals("pop_front")) {

                System.out.println(list.pollFirst());
            
            } else if(q.equals("pop_back")) {

                System.out.println(list.pollLast());

            } else if(q.equals("size")) {

                System.out.println(list.size());
            } else if(q.equals("empty")) {
                
                if(list.isEmpty() == true) {
                    System.out.println(1);
                } else {
                    System.out.println(0);
                }

            } else if(q.equals("front")) {

                System.out.println(list.peekFirst());

            } else {
                System.out.println(list.peekLast());
            }
        }
    }
}

 

 

6. 원하는 값이 든 노드를 삭제하기

 

head에서 시작해서 인자로 받은 값과 일치하는 값을 가지는 노드를 찾아 삭제하는 메소드 구현해보기

 

node.next가 None이 아닐때까지 head에서 반복적으로 탐색을 수행

 

node.data가 들어온 값 data와 일치한다면 반복문 탈출

 

그렇지 않다면 다음 노드 node.next로 이동

 

반복문을 탈출했다면 현재 node를 삭제하고 싶으므로... node.next의 prev는 현재 node의 prev로 연결

 

node.prev의 next는 현재 node의 next로 연결

 

 

 

def head_search_delete(self,data):
    
    node = self.head
    
    while node.next != None:
        
        if node.data == data:
            break
        
        node = node.next
    
    node.next.prev = node.prev
    node.prev.next = node.next

 

반대로 tail에서 시작해서 원하는 값과 일치하는 노드를 찾아 삭제하는 메소드도 구현해볼 수 있을 것이다.

 

시작 노드를 self.tail로 하고

 

현재 node의 데이터가 num과 다르다면 node.prev로 반복 이동하고 같다면 반복문 탈출

 

탈출한 순간 node를 지워야하니까..

 

node의 prev와 next를 서로 연결시켜줘야함

 

지워야하는 node 왼쪽

 

 node.prev는 지워야하는 node 오른쪽 node.next의 prev

 

지워야하는 node 오른쪽 node.next는 지워야하는 node 왼쪽 node.prev의 next

 

def tail_search_delete(self,num):
    
    node = self.tail
    
    while node.data != num:
        
        node = node.prev
    
    node.next.prev = node.prev
    node.prev.next = node.next

 

 

7. 파이썬에서 이중연결리스트

 

파이썬에서는 이중연결리스트 구현체에 해당하는 class가 없어서 직접 class를 정의해서 구현해줘야한다.

 

제대로 구현된 코드를 따라 쳐보면서 복습하고 마무리

 

#Node class를 만든다

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


#이중 연결리스트 class를 만든다

class DoublyLinkedList:
    
    def __init__(self):
        
        self.head = None
        self.tail = None
        self.node_num = 0
    

    #원소를 맨 앞에 넣는 메소드
    def push_front(self, new_data):
        
        #새로운 노드를 만든다
        new_node = Node(new_data)

        #새로운 노드의 next값을 현재 head로 변경
        new_node.next = self.head

        #기존 이중연결리스트가 비어있지 않다면..
        if self.head != None:
            
            #현재 head의 prev를 새로운 node로 변경
            self.head.prev = new_node

            #head를 새로운 노드로 변경
            self.head = new_node

            #head로 들어가는 노드의 prev는 없다
            new_node.prev = None
        
        #기존 이중연결리스트가 비어있다면..
        else:
            
            #새로들어온 노드가 head이면서 tail
            self.head = new_node
            self.tail = new_node
            new_node.prev = None
        
        #새로 값이 들어왔으니까
        self.node_num += 1
    

    #원소를 맨 끝 위치에 넣는 메소드
    def push_back(self,new_data):
        
        #새로운 노드를 만든다
        new_node = Node(new_data)

        #새로운 노드의 prev값을 현재 리스트의 tail로 변경
        new_node.prev = self.tail

        #현재 리스트가 비어있지 않다면
        if self.tail != None:
            
            #이전 tail의 next를 새로운 노드로 바꾸고
            self.tail.next = new_node

            #tail을 새로운 노드로 변경
            self.tail = new_node

            #새로운 노드의 next는 없다
            new_node.next = None
        
        #기존 리스트가 비어있다면
        else:
            
            #head와 tail이 새로만든 노드와 동일
            self.head = new_node
            self.tail = new_node
            new_node.next = None
        
        self.node_num += 1
    

    #첫번째 수를 빼면서 동시에 그 수를 반환하는 메소드

    def pop_front(self):
        
        #노드가 없다
        if self.head == None:
            
            print("List is empty")
        
        #노드가 오직 하나
        elif self.head.next == None:
            
            temp = self.head

            #head,tail 모두 삭제하고 노드 수는 0개
            self.head = None
            self.tail = None
            self.node_num = 0

            return temp.data
        
        #노드가 2개이상
        else:
            
            temp = self.head
            
            #temp.next의 prev(현재 head)를 지워주고
            temp.next.prev = None

            #head를 현재 head의 next로 변경
            self.head = temp.next

            #현재 head인 temp의 next를 지워주고
            temp.next = None

            self.node_num -= 1
            return temp.data
    

    #맨 끝에 있는 수를 빼면서 동시에 그 수를 반환

    def pop_back(self):
        
        #노드가 하나도 없다
        if self.tail == None:
            
            print("List is empty")
        
        #노드가 오직 하나
        elif self.tail.prev == None:
            
            temp = self.tail

            #head,tail 모두 삭제, node_num을 0으로
            self.head = None
            self.tail = None
            self.node_num = 0

            return temp.data
        
        #노드가 둘 이상
        else:
            
            temp = self.tail

            #새로 tail이 될 노드의 next값을 지워준다
            temp.prev.next = None

            #tail을 갱신
            self.tail = temp.prev

            #이전 tail이 든 temp의 prev를 제거해서 이전 tail을 완전히 삭제
            temp.prev = None

            #노드 하나 지웠으니 노드 수 하나 감소
            self.node_num -= 1
            return temp.data
    
    #노드의 수를 반환
    def size(self):
        
        return self.node_num
    
    #연결리스트가 비었는지 여부
    def empty(self):
        
        return self.node_num == 0
    
    #첫번째 수를 단순히 반환

    def front(self):
        
        if self.head == None:
            
            print("List is empty")
        
        else:
            
            return self.head.data
    

    #마지막 수를 반환

    def back(self):
        
        if self.tail == None:
            print("List is empty")
        else:
            return self.tail.data


l = DoublyLinkedList()

l.push_front(3)
l.push_front(5)

print(l.front()) #5
print(l.back()) #3

l.push_back(9)
print(l.back()) #9

l.pop_front()
print(l.front()) #3

print(l.size()) #2

'알고리즘 > Java 기초' 카테고리의 다른 글

자바 초보부터 B형까지6 -함수 작성법 필수-  (0) 2023.03.01
자바 초보에서 B형까지5 -문자열 필수지식-  (0) 2023.02.26
핵심 자료구조 기본인 단일 연결리스트(linked list) 개념파악하기  (0) 2023.02.24
자바 자료구조1 -동적배열(ArrayList)  (0) 2023.02.23
자바 초보에서 알고리즘 B형까지 도전기4 -배열 필수지식1-  (0) 2023.02.22
TAGS.

Comments