search
Home类库下载java类库JAVA linked list operation
JAVA linked list operationOct 19, 2016 am 09:48 AM

1. Single linked list circular linked list

package LinkListTest;

import java.util.HashMap;
import java.util.Map;

public class SingleCycleLinkList implements ICommOperate<SNode> {
    private SNode head = new SNode("HEAD") ; // 公共头指针,声明之后不变
    private int size = 0 ;
    public int getSize() {
        return this.size;
    }
    
    /*
     * 链表插入,每次往末端插入,判定末端的标准为next是否指向head
     * */
    @Override
    public boolean insertNode(SNode node) {
        boolean flag = false  ; 
        
        initLinkList() ; // 初始化链表
        if( this.size==0 ){  // 空链表
            this.head.setNextNode(node) ;
            node.setNextNode(this.head) ;
        }else{
            SNode current = this.head ;
            while( current.getNextNode()!=this.head ){ // 找到末端节点
                current = current.getNextNode() ;
            }
            current.setNextNode(node) ;
            node.setNextNode(this.head) ; // 循坏链表,尾节点指向head
        }
        this.size++ ;
        flag = true ;
        
        return flag;
    }
    
    /*
     * 插入链表指定位置pos,从1开始,而pos大于size则插入链表末端
     * */
    @Override
    public boolean insertPosNode(int pos, SNode node) {
        boolean flag = true ; 
        SNode current = this.head.getNextNode() ;
        
        initLinkList() ;// 初始化链表
        if( this.size==0 ){                 // 链表为空
            this.head.setNextNode(node) ;
            node.setNextNode(this.head) ;// 循坏链表,尾节点指向head
            this.size++ ;
        }else if( this.size<pos ){           // pos位置大于链表长度,插入末端
            insertNode(node) ;
        }else if( pos>0 && pos<=this.size ){ // 链表内节点
            // 1、找到要插入pos位置节点和前节点,node将插入两个节点之间
            int find = 0;
            SNode preNode = this.head; // 前节点
            SNode currentNode = current; // 当前节点
            while( find<pos-1 && currentNode!=this.head ){
                preNode = current ;                          // 前节点后移
                currentNode = currentNode.getNextNode() ; // 当前节点后移
                find++ ;
                if( find<pos-1 && currentNode!=this.head ){ // 未结束寻找节点前,后移前节点
                    current = current.getNextNode() ;
                }
            }
//            System.out.println(preNode);
//            System.out.println(currentNode);
            
            // 2、插入节点
            preNode.setNextNode(node);
            node.setNextNode(currentNode);
            this.size++ ;
        }else {
            System.out.println("位置信息错误");
            flag = false ;
        }
        
        return flag;
    }

    private void initLinkList(){
        if( size==0 ){
            this.head.setNextNode(this.head);
        }
    }
    
    /*
     * 指定链表的节点pos,删除对应节点。方式:找到要删除节点的前后节点,进行删除,下标从1开始
     * */
    @Override
    public boolean deleteNode(int pos) {
        boolean flag = false; 
        SNode current = this.head.getNextNode() ;
        if( pos<=0 || pos>this.size || current==this.head ){
            System.out.println("位置信息错误或链表无信息");
        }else{
            // 1、找到要删除节点的前后节点
            int find = 0;
            SNode preNode = this.head; // 前节点
            SNode nextNode = current.getNextNode(); // 后节点
            while( find<pos-1 && nextNode!=this.head ){
                preNode = current ;                    // 前节点后移
                nextNode = nextNode.getNextNode() ; // 后节点后移
                find++ ;
                if( find<pos-1 && nextNode!=this.head ){ // 未结束找节点前,后移"前节点"
                    current = current.getNextNode() ;
                }
            }
//            System.out.println(preNode);
//            System.out.println(nextNode);
            
            // 2、删除节点
            preNode.setNextNode(nextNode);
            System.gc(); // 回收删除节点
            this.size-- ;
            flag = true ;
        }
        
        return flag;
    }
    
    /*
     * 指定链表的节点pos,修改对应节点,下标从1开始
     * */
    @Override
    public boolean updateNode(int pos, Map<String, Object> map) {
        boolean flag = false ;
        SNode node = getNode(pos, map); // 获得相应位置pos的节点
        if( node!=null ){
            String data = (String) map.get("data") ;
            node.setData(data);
            flag = true ;
        }
        return flag;
    }
    
    /*
     * 找到指定链表的节点pos,下标从1开始
     * */
    @Override
    public SNode getNode(int pos, Map<String, Object> map) {
        SNode current = this.head.getNextNode() ;
        if( pos<=0 || pos>this.size || current==this.head ){
            System.out.println("位置信息错误或链表不存在");
            return null;
        }
        int find = 0 ;
        while( find<pos-1 && current!=this.head ){
            current = current.getNextNode() ;
            find++ ;
        }
        return current;
    }

    /*
     * 打印链表
     * */
    @Override
    public void printLink() {
        int length = this.size ;
        if( length==0 ){
            System.out.println("链表为空!");
            return ;
        }
        SNode current = this.head.getNextNode() ;
        System.out.println("总共有节点数: " + length +" 个");
        int find = 0 ;
        while( current!=this.head ){
            System.out.println("第 " + (++find) + " 个节点 :" + current);
            current=current.getNextNode() ;
        }
    }
    
    public static void main(String[] args) {
        SingleCycleLinkList scll = new SingleCycleLinkList() ;
        SNode node1 = new SNode("节点1");
        SNode node2 = new SNode("节点2");
        SNode node3 = new SNode("节点3");
        SNode node4 = new SNode("节点4");
        SNode node5 = new SNode("节点5");
        SNode node6 = new SNode("插入指定位置");
//        scll.insertPosNode(scll.getSize()+1, node1) ;
//        scll.insertPosNode(scll.getSize()+1, node2) ;
//        scll.insertPosNode(scll.getSize()+1, node3) ;
//        scll.insertPosNode(scll.getSize()+1, node4) ;
//        scll.insertPosNode(scll.getSize()+1, node5) ;
        scll.insertNode(node1);
        scll.insertNode(node2);
        scll.insertNode(node3);
        scll.insertNode(node4);
        scll.insertNode(node5);
        
        System.out.println("*******************输出链表*******************");
        scll.printLink();
        
        System.out.println("*******************获得指定链表节点*******************");
        int pos = 2 ;
        System.out.println("获取链表第 "+pos+" 个位置数据 :"+scll.getNode(pos, null));
        
        System.out.println("*******************向链表指定位置插入节点*******************");
        int pos1 = 3 ;
        System.out.println("将数据插入第"+pos1+"个节点:");
        scll.insertPosNode(pos1, node6) ;
        scll.printLink();
        
        System.out.println("*******************删除链表指定位置节点*******************");
        int pos2 = 3 ;
        System.out.println("删除第"+pos2+"个节点:");
        scll.deleteNode(pos2) ;
        scll.printLink();
        
        System.out.println("*******************修改链表指定位置节点*******************");
        int pos3 = 3 ;
        System.out.println("修改第"+pos3+"个节点:");
        Map<String, Object> map = new HashMap<>() ;
        map.put("data", "this is a test") ;
        scll.updateNode(pos3, map) ;
        scll.printLink();
    }

}

2. Double linked list circular linked list

package LinkListTest;

import java.util.HashMap;
import java.util.Map;

public class DoubleCycleLinkList implements ICommOperate<DNode>{
    private DNode head = new DNode("HEAD"); // 公共头指针,声明之后不变
    private int size = 0 ; // 记录链表节点数量
    
    public int getSize() {
        return this.size;
    }
    
    /*
     * 链表插入,每次往末端插入,判定末端的标准为next是否指向head
     * */
    @Override
    public boolean insertNode(DNode node) {
        boolean flag = false ; 
        
        initLinkList() ; // 初始化链表
        DNode current = this.head ;
        if( this.size==0 ){    // 空链表
            this.head.setNextNode(node) ;
            node.setPriorNode(this.head);
            node.setNextNode(this.head) ;
        }else{                // 链表内节点
            while( current.getNextNode()!=this.head ){ // 找到末端节点
                current = current.getNextNode() ;
            }
            current.setNextNode(node) ;
            node.setPriorNode(current);
            node.setNextNode(this.head) ; // 循坏链表,尾节点指向head
        }
        this.size++ ;
        flag = true ;
        
        return flag;
    }
    
    /*
     * 插入链表指定位置pos,从1开始,而pos大于size则插入链表末端
     * */
    @Override
    public boolean insertPosNode(int pos, DNode node) {
        boolean flag = true; 
        
        initLinkList() ; // 初始化链表
        DNode current = this.head.getNextNode() ;
        if( this.size==0 ){                     // 链表为空
            this.head.setNextNode(node) ;
            node.setPriorNode(this.head);
            node.setNextNode(this.head) ;
            this.size++ ;
        }else if( pos>this.size ){                 // pos位置大于链表长度,插入末端
            insertNode(node) ;
        }else if( pos>0 && pos<=this.size ){    // 链表内节点
            // 1、找到要插入位置pos节点,插入pos节点当前位置
            int find = 0;
            while( find<pos-1 && current.getNextNode()!=this.head ){
                current = current.getNextNode() ;
                find++ ;
            }
            // 2、插入节点
            if( current.getNextNode()==this.head ){ // 尾节点
                node.setPriorNode(current);
                node.setNextNode(this.head);
                current.setNextNode(node);
            } else if( current.getNextNode()!=this.head ) {  //中间节点
                node.setPriorNode(current.getPriorNode());
                node.setNextNode(current);
                current.getPriorNode().setNextNode(node);
                current.setPriorNode(node);
            } 
            this.size++ ;
        }else{
            System.out.println("位置信息错误");
            flag = false ;
        }
        return flag;
    }

    private void initLinkList(){
        if( size==0 ){
            this.head.setNextNode(this.head);
            this.head.setPriorNode(this.head);
        }
    }
    
    /*
     * 指定链表的节点pos,删除对应节点。方式:找到要删除节点的前后节点删除,下标从1开始
     * */
    @Override
    public boolean deleteNode(int pos) {
        boolean flag = false; 
        DNode current = this.head.getNextNode() ;
        if( pos<=0 || pos>this.size || current==this.head ){
            System.out.println("位置信息错误或链表不存在");
        }else{
            // 1、找到要删除位置pos节点
            int find = 0;
            while( find<pos-1 && current.getNextNode()!=this.head ){
                current = current.getNextNode() ;
                find++ ;
            }
            // 2、删除节点
            if( current.getNextNode()==this.head ){ // 尾节点
                current.getPriorNode().setNextNode(this.head) ;
            } else if( current.getNextNode()!=this.head ) {  //中间节点
                current.getPriorNode().setNextNode(current.getNextNode()) ;
                current.getNextNode().setPriorNode(current.getPriorNode()) ;
            } 
            System.gc(); // 回收删除节点
            this.size-- ;
            flag = true ;
        }
        return flag;
    }
    
    /*
     * 指定链表的节点pos,修改对应节点,下标从1开始
     * */
    @Override
    public boolean updateNode(int pos, Map<String, Object> map) {
        boolean flag = false ;
        DNode node = getNode(pos, map);
        if( node!=null ){
            String data = (String) map.get("data") ;
            node.setData(data);
            flag = true ;
        }
        return flag;
    }

    /*
     * 找到指定链表的节点pos,下标从1开始
     * */
    @Override
    public DNode getNode(int pos, Map<String, Object> map) {
        DNode current = this.head.getNextNode() ;
        if( pos<=0 || pos>this.size || current==this.head ){
            System.out.println("位置信息错误或链表不存在");
            return null;
        }
        int find = 0 ;
        while( find<pos-1 && current!=this.head ){
            current = current.getNextNode() ;
            find++ ;
        }
        return current;
    }

    /*
     * 打印链表
     * */
    @Override
    public void printLink() {
        int length = this.size ;
        if( length==0 ){
            System.out.println("链表为空!");
            return ;
        }
        DNode current = this.head.getNextNode() ;
        int find = 0 ; 
        System.out.println("总共有节点数: " + length +" 个");
        while( current!=this.head ){
            System.out.println("第 " + (++find) + " 个节点 :" + current);
            current=current.getNextNode() ;
        }
    }
    
    public static void main(String[] args) {
        DoubleCycleLinkList dcll = new DoubleCycleLinkList() ;
        DNode node1 = new DNode("节点1");
        DNode node2 = new DNode("节点2");
        DNode node3 = new DNode("节点3");
        DNode node4 = new DNode("节点4");
        DNode node5 = new DNode("节点5");
        DNode node6 = new DNode("插入指定位置");
        dcll.insertPosNode(10, node1) ;
        dcll.insertPosNode(10, node2) ;
        dcll.insertPosNode(8, node3) ;
        dcll.insertPosNode(88, node4) ;
        dcll.insertPosNode(8, node5) ;
//        dcll.insertNode(node1);
//        dcll.insertNode(node2);
//        dcll.insertNode(node3);
//        dcll.insertNode(node4);
//        dcll.insertNode(node5);
        
        System.out.println("*******************输出链表*******************");
        dcll.printLink();
        
        System.out.println("*******************获得指定链表节点*******************");
        int pos = 2 ;
        System.out.println("获取链表第 "+pos+"个位置数据 :"+dcll.getNode(pos, null));
        
        System.out.println("*******************向链表指定位置插入节点*******************");
        int pos1 = dcll.getSize()+1 ;
        System.out.println("将数据插入第"+pos1+"个节点:");
        dcll.insertPosNode(pos1, node6) ;
        dcll.printLink();
        
        System.out.println("*******************删除链表指定位置节点*******************");
        int pos2 = 7 ;
        System.out.println("删除第"+pos2+"个节点:");
        dcll.deleteNode(pos2) ;
        dcll.printLink();
        
        System.out.println("*******************修改链表指定位置节点*******************");
        int pos3 = 3 ;
        System.out.println("修改第"+pos3+"个节点:");
        Map<String, Object> map = new HashMap<>() ;
        map.put("data", "this is a test") ;
        dcll.updateNode(pos3, map) ;
        dcll.printLink();
    }
}


Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools