[자료구조] Linked List

연결 리스트 (Linked List)

연결될 다음 운소에 대한 주소를 저장해야 하므로 <data + link> 의 단위로 저장한다.(이와 같은 단위를 Node 라고 함)

즉, 시작(주소) - 연결(Link) - 끝(Null Pointer or Circular) 와 같은 순서가 존재

 

1. 단순 연결 리스트 (Singly Linked List)

Singly Linked List (단일 연결 리스트)

2. 원형 연결 리스트 (Circular Linked List)

Circular Linked List (원형 연결 리스트)

3. 이중 연결 리스트 (Doubly Linked List)

Doubly Linked List (이중 연결 리스트)

 

 Linked List 예제 

package linkedList;

public interface LinkedList {
    ListNode add(ListNode head, ListNode nodeToAdd, int position);
    ListNode remove(ListNode head, int positionToRemove);
    void printList(ListNode head);
    boolean contains(ListNode head, ListNode nodeToCheck);
}

package linkedList;

public class ListNode implements LinkedList{
    int data;
    private ListNode next;

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

    public ListNode() {

    }

    @Override
    public ListNode add(ListNode head, ListNode nodeToAdd, int position) {
        // 초기 상태
        if (position == 0 && head == null) {
            head = nodeToAdd;
            return head;
        }
        // 맨 앞에 add
        else if (position == 0){
            nodeToAdd.next = head;
            head = nodeToAdd;

            return head;
        }

        ListNode node = head;
        // find pos
        for (int i = 0; i < position - 1; i++) {
            node = node.next;
        }
        // 해당 pos에 add
        nodeToAdd.next = node.next;
        node.next = nodeToAdd;
        return head;
    }
    @Override
    public ListNode remove(ListNode head, int positionToRemove) {
        if (positionToRemove == 0) {
            head = head.next;
            return head;
        }
        else {
            ListNode node = head;
            for(int i=0; i< positionToRemove; i++) {
                node = node.next;
            }
            node.next = node.next.next;
            return head;
        }
    }

    @Override
    public void printList(ListNode head) {
        ListNode node = head;
        while (node != null) {
            System.out.print(node.data);
            node = node.next;
        }
        System.out.println();
    }

    @Override
    public boolean contains(ListNode head, ListNode nodeToCheck) {
        ListNode node = head;
        while(node != null) {
            if (node.data == nodeToCheck.data) {
                return true;
            }
            node = node.next;
        }
        return false;
    }
    public static void main(String[] args)  {
        LinkedList nums = new ListNode();

        ListNode head = null;
        for(int i=0; i<5; i++) {
            head = nums.add(head, new ListNode(i), i);
        }
        nums.printList(head);
        head = nums.remove(head, 0);
        head = nums.remove(head, 0);
        nums.printList(head);
        System.out.println(nums.contains(head, new ListNode(3)));
        System.out.println(nums.contains(head, new ListNode(1)));
    }
}

package linkedList;


public class ListNodeStack {
	
	private ListNode head;
	private int top;
	
	public ListNodeStack() {
		this.head = new ListNode();
		this.top = -1;
	}
	public void push(int data) {
		ListNode listNode = new ListNode(data);
		head.add(this.head, listNode, ++top);
	}
	public int pop() {
		if(top == -1) {
			System.out.println("Empty");
			return top;
		}
		return head.remove(head,--top).data;
	}
	public void print() {
		head.printList(head);
	}
	public static void main(String[] args) {
		ListNodeStack listNodeStack = new ListNodeStack();
		
		for(int i=0; i<5; i++) {
			listNodeStack.push(i);
		}
		listNodeStack.print();
		listNodeStack.pop();
		listNodeStack.print();
	}
}