자료구저 - 연결리스트 (Linked List ) JAVA

연결리스트 (Linked List)

• 데이터를 링크로 연결해서 관리하는 자료구조
• 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장 X

연결리스트 장점

• 데이터 공간을 미리 할당할 필요 x
• 리스트 길이가 가변적이라 데이터 추가/삭제 용이

연결리스트 단점

• 연결구조를 위한 별도 데이터가 필요
• 연결 정보를 찾는 시간이 필요하다
• 추가, 삭제 시 앞뒤 데이터 연결을 할 작업이 필요

---

 

 

연결리스트의 기본 구조 이다.

 

 

 

 

연결리스트의 삭제하기 위해선 head의 위치를 변경하거나 Next의 위치를 변경하는 구조가 필요함

 

 

JAVA 소스 코드

class Node{
    int data;
    Node next;

    Node (){}
    Node (int data, Node next){
        this.data = data;
        this.next = next;
    }
}
class LLlist {
    Node head;
    LLlist(){}
    LLlist(Node node){
        this.head = node;
    }
    public boolean isEmpth(){
        if(this.head == null){
            return true;
        }return false;
    }

 

연결리스트를 생성하기 위해서는 기본적으로 Node  =  data, next 구조가 필요하다 

 

 public void addData (int data){
        if (this.head == null){
            this.head = new Node(data, null);
        }else{
            Node cur = this.head;
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = new Node(data, null);
        }
    }

연결리스트에 데이터를 추가하는 함수이다. head 가 비어있다면 첫생성이므로 this.head 현제 head에 노드를 추가한다

데이터를 추가할 때에는 데이터를 추가해야할 위치도 필요하기때문에 cur 라는 클래스 변수를 잡아준뒤 cur 의 위치를 순회 하며 마지막에 추가해준다 

만약 데이터와 추가해줘야할 데이터 위치가 있다면 prev 라는 클래스 변수를 생성하여 쫓아가면서 추가할 위치조건이 맞을경우에 생성해주면 된다.

 

 

 public void removeData(int data){
        if(this.isEmpth()){
            return;
        }
        Node cur = this.head;
        Node prev = cur;
        while(cur.next != null){
            if(cur.data == data){
                if(cur == this.head){
                    this.head = cur.next;
                }else{
                    prev.next = cur.next;
                }
                break;
            }
            prev = cur;
            cur = cur.next;
        }

 

 

 

기본적인 단방향 연결리스트는 add , remove 구조만 잘 이해하고있다면 구현에서 어려운 부분은 없다고 생각한다.

 

양방향이어렵다