𝙇𝙞𝙣𝙠𝙚𝙙𝙇𝙞𝙨𝙩

uuuouuo·2022년 7월 20일

단순연결리스트 연결리스트 이중연결리스트

📖 연결 리스트

💬 단순 연결 리스트

LinkedList의 경우 ArrayList와 다른게 노드라는 객체를 이용
노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조
단방향으로 연결 된 리스트
헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킴
최종적으로 null을 가리키는 노드가 리스트의 마지막 노드

◾ 단순 연결 리스트의 단점

한번 순회하면 이전 노드로 돌아가는 것 불가능
- 원하는 노드를 지나쳤다면 처음부터 다시 순회

단순 연결 리스트

노드: 자신의 데이터 + 다음 노드의 주소값 형태

◾ 구현

노드

class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null; // 다음 노드 data 저장
    }
}

Main Class

초기 세팅

    private final static int MAX_NODE = 10000;

    private Node[] node = new Node[MAX_NODE];
    private int nodeCnt = 0;
    private Node head;

    public Node getNode(int data) { // 새로운 node 할당
        node[nodeCnt] = new Node(data);
        return node[nodeCnt++];
    }

    public void init() {
        head = null;
    }

head 삽입

만약 헤드가 존재하지 않는다면, 전달된 data가 헤드
이미 헤드가 존재한다면, 새로운 노드가 현재 노드를 가리키도록 함

    public void addNode2Head(int data) {
        if (head == null) {
            head = getNode(data);
            return;
        }

        Node nHead = getNode(data);
        nHead.next = head;
        head = nHead;
    }

tail 삽입

만약 헤드가 존재하지 않는다면, 전달된 data가 헤드
헤드부터 순회해서 마지막 노드 찾은 후 새로운 노드를 가리키도록 함

 public void addNode2Tail(int data) {
        if (head == null) {
            head = getNode(data);
            return;
        }

        Node curNode = head; // head 찾아서 tail 찾아야함
        while (curNode.next != null) { // 현재 node next가 null인 지점 찾기
            curNode = curNode.next; // null이 아니라면 다음 next node가 cur
        }

        Node nTail = getNode(data); // 새로운 tail 생성
        curNode.next = nTail;
    }

해당 data를 num번째에 삽입

num번째의 노드 찾은 후 이전 노드는 새로운 노드를 가리키게 함
그리고 새로운 노드는 기존 num번째 노드를 가리키게 함

public void addNode2Num(int data, int num) {
        if (head == null) {
            head = getNode(data);
            return;
        }
        if (num == 1) { // 맨앞에 넣을 경우
            addNode2Head(data);
            return;
        }

        Node curNode = head;
        Node preNode = null;
        int cnt = 1;
        while (true) {
            if (cnt == num - 1) {
            	if (curNode == null) { // 연결 노드 개수보다 큰 경우 마지막에 삽입
            		addNode2Tail(data);
            		return;
        	  	}
                preNode = curNode;
                curNode = curNode.next;
                break;
            }
            curNode = curNode.next;
            cnt++;
        }

        Node nNode = getNode(data);
        preNode.next = nNode;
        nNode.next = curNode;

    }

해당 data가 있는 노드 삭제

해당 노드 찾은 후 해당 노드의 이전 노드가 해당 노드의 다음 노드를 가리키게 함
만약 해당 data를 가지고 있는 노드가 없다면 return

public void removeNode(int data) {
        if (head.data == data) {
            head = head.next;
            return;
        }

        Node curNode = head;
        Node preNode = null;
        Node nextNode = null;
        while (true) {
            if (curNode == null)
                return;

            if (curNode.data == data) {
                nextNode = curNode.next;
                break;
            }
            preNode = curNode;
            curNode = curNode.next;
        }

        preNode.next = nextNode;

    }