真正的数据结构和算法【5】

单链表

通用存储结构

链表LinkList:第一个链结点 --> 第二个链结点

链结点Link:next,Data,

删除数据项非常简单

单链表 从首节点插入;

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link;

/**
 * @author Zen
 * @version 1.0: SingleLink.java, v 0.1 2019/05/14 8:59 Zen Exp $
 */
public class SingleLink {
    public int data;
    public SingleLink next;

    public SingleLink(int d){
        this.data = d;
    }

    @Override
    public String toString() {
        return "SingleLink{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link;

/**
 * @author Zen
 * @version 1.0: SingleLinkList.java, v 0.1 2019/05/14 9:02 Zen Exp $
 */
public class SingleLinkList {
    private SingleLink first;

    public SingleLinkList(){
        first = null;
    }

    public boolean isEmpty(){
        return first == null;
    }

    public void insert(int value){
        SingleLink newLink = new SingleLink(value);
        newLink.next = first;
        first = newLink;
    }

    public SingleLink delete(){
        SingleLink singleLink = first;
        first = first.next;
        return singleLink;
    }

    public void displayAll(){
        SingleLink currentLink = first;
        while(currentLink != null){
            System.out.println(currentLink.toString());
            currentLink = currentLink.next;
        }
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link;

/**
 * @author Zen
 * @version 1.0: SingleLinkListApp.java, v 0.1 2019/05/14 9:13 Zen Exp $
 */
public class SingleLinkListApp {
    public static void main(String[] args) {
        SingleLinkList list = new SingleLinkList();
        list.insert(101);
        list.insert(102);
        list.insert(103);
        list.insert(104);
        list.insert(105);
        list.insert(106);
        list.insert(107);
        list.insert(108);
        list.insert(109);
        list.displayAll();
        list.delete();
        list.delete();
        list.displayAll();

    }
}

双端链表介绍
Java代码实现双端链表结构
链表效率

单链表中增加了一个数据项,last的位置,last指向最后一个结点

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.first_last_link;

/**
 * @author Zen
 * @version 1.0: Link.java, v 0.1 2019/05/15 13:20 Zen Exp $
 */
public class Link {
    public int data;
    public Link next;
    public Link(int value){
        this.data = value;
    }

    @Override
    public String toString() {
        return "Link{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }

}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.first_last_link;

/**
 * @author Zen
 * @version 1.0: FirstLaskLink.java, v 0.1 2019/05/15 13:22 Zen Exp $
 */
public class FirstLaskLink {
    public Link first;
    public Link last;

    public FirstLaskLink(){
        first = null;
        last = null;
    }
    public boolean isEmpty(){
        return first==null;
    }
    public void insertFirst(int dd) {
        Link newLink = new Link(dd);
        if(isEmpty()){
            last = newLink;
        }
        newLink.next = first;
        first = newLink;
    }
    public void insertLast(int dd){
        Link newLink = new Link(dd);
        if(isEmpty()){
            first = newLink;
        }else{
            last.next = newLink;
        }
        last = newLink;
    }

    public int deleteFirst(){
        int temp = first.data;
        if(first.next ==null){
            last = null;
        }
        first = first.next;
        return temp;
    }
    public void displayAll(){
        System.out.println("List(first-->last)");
        Link current = first;
        while(current.next!= null){
            System.out.print(current);
            current = current.next;
        }
        System.out.println();
    }

}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.first_last_link;

/**
 * @author Zen
 * @version 1.0: FirstLastLinkApp.java, v 0.1 2019/05/15 13:35 Zen Exp $
 */
public class FirstLastLinkApp {
    public static void main(String[] args) {
        FirstLaskLink theList = new FirstLaskLink();
        theList.insertFirst(22);
        theList.insertFirst(22);
        theList.insertFirst(22);
        theList.insertFirst(22);
        theList.insertFirst(22);
        theList.insertFirst(22);
        theList.insertFirst(22);
        theList.insertFirst(28);
        theList.displayAll();
        theList.deleteFirst();
        theList.deleteFirst();
        theList.displayAll();

    }
}

链表_抽象数据类型

任何一个类都是一种数据类型

当一个数据存储结构表示为一个类的情况下,这个类也就成为一个数据类型。

抽象:意思就是不考虑细节的描述和实现。

栈和队列就是抽象数据类型
栈的特点:先进后出
队列的特点:先进先出
抽象数据类型:ADT

用Link做栈和队列

用链表做栈

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.linkstack;

/**
 * @author Zen
 * @version 1.0: Link.java, v 0.1 2019/05/15 15:02 Zen Exp $
 */
public class Link {
    public int data;
    public Link next;
    public Link(int value){
        this.data = value;
    }
    @Override
    public String toString() {
        return "Link{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.linkstack;

/**
 * @author Zen
 * @version 1.0: LinkList.java, v 0.1 2019/05/15 15:04 Zen Exp $
 */
public class LinkList {
    public Link first;
    public LinkList(){
        first = null;
    }
    public void insertFirst(int value){
        Link newLink = new Link(value);
        newLink.next = first;
        first = newLink;
    }
    public int deleteFirst(){
        Link deleteLink = first;
        first = first.next;
        return deleteLink.data;
    }
    public void display(){
        Link currentLink = first;
        while(currentLink.next != null){
            System.out.print(currentLink);
            currentLink = currentLink.next;
        }
        System.out.println();
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.linkstack;

/**
 * @author Zen
 * @version 1.0: LinkListStack.java, v 0.1 2019/05/15 15:20 Zen Exp $
 */
public class LinkListStack {
    LinkList list;
    LinkListStack(){
        list = new LinkList();
    }
    public void push(int value){
        list.insertFirst(value);
    }
    public void pop(){
        int delete = list.deleteFirst();
        System.out.println("被删除元素为:"+delete);
    }
    public void displayAll(){
        list.display();
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.linkstack;

/**
 * @author Zen
 * @version 1.0: LinkListStackApp.java, v 0.1 2019/05/15 15:25 Zen Exp $
 */
public class LinkListStackApp {
    public static void main(String[] args) {
        LinkListStack stack = new LinkListStack();
        stack.push(101);
        stack.push(102);
        stack.push(103);
        stack.push(104);
        stack.push(105);
        stack.push(106);
        stack.push(107);
        stack.push(108);
        stack.push(109);
        stack.displayAll();
        stack.pop();
        stack.pop();
        stack.displayAll();

    }
}

双端链表实现队列

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.linkqueue;

/**
 * @author Zen
 * @version 1.0: Link.java, v 0.1 2019/05/15 15:02 Zen Exp $
 */
public class Link {
    public int data;
    public Link next;
    public Link(int value){
        this.data = value;
    }
    @Override
    public String toString() {
        return "Link{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.linkqueue;


/**
 * @author Zen
 * @version 1.0: FirstLastLinkList.java, v 0.1 2019/05/15 15:34 Zen Exp $
 */
public class FirstLastLinkList {
    public Link first;
    public Link last;
    public FirstLastLinkList(){
        first = null;
        last = null;
    }
    public boolean isEmpty(){
        return last == null;
    }
    public void insertFirst(int value){
        Link  newLink = new Link(value);
        if(isEmpty()){
            last = newLink;
        }
        newLink.next = first;
        first = newLink;
    }
    public void insertLast(int value){
        Link newLink = new Link(value);
        if(isEmpty()){
            first = newLink;
        }else{
            last.next = newLink;
        }
        last = newLink;
    }

    public int deleteFirst(){
        Link deleted = first;
        first = first.next;
        return deleted.data;
    }
    public void display(){
        Link currentLink = first;
        while(currentLink != null){
            System.out.print(currentLink);
            currentLink = currentLink.next;
        }
        System.out.println();
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.linkqueue;



/**
 * @author Zen
 * @version 1.0: LinkListQueue.java, v 0.1 2019/05/15 15:46 Zen Exp $
 */
public class LinkListQueue {
    FirstLastLinkList list;
    public LinkListQueue(){
        list = new FirstLastLinkList();
    }

    public void insert(int value){
        list.insertLast(value);
    }

    public void remove(){
        int deleted = list.deleteFirst();
        System.out.println("删除的元素为:"+deleted);
    }
    public void displayAll(){
        list.display();
    }

}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package link.linkqueue;

/**
 * @author Zen
 * @version 1.0: LinkListQueueApp.java, v 0.1 2019/05/15 15:53 Zen Exp $
 */
public class LinkListQueueApp {
    public static void main(String[] args) {
        LinkListQueue queue = new LinkListQueue();
        queue.insert(110);
        queue.insert(120);
        queue.insert(130);
        queue.insert(140);
        queue.insert(220);
        queue.insert(230);
        queue.insert(200);
        queue.insert(200);
        queue.insert(200);
        queue.insert(200);
        queue.displayAll();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.displayAll();
    }
}

本文链接:

https://heyzen.club/index.php/Coder/302.html
1 + 3 =
快来做第一个评论的人吧~