实现基础的单链表及链表反转

    1. public class Node<T> {
    2.     private T data;
    3.     private Node<T> next;
    5.     public Node(T data, Node<T> next) {
    6.         this.data = data;
    7.         this.next = next;
    8.     }
    10.     public T getData() {
    11.         return data;
    12.     }
    14.     public void setData(T data) {
    15.         this.data = data;
    16.     }
    18.     public Node<T> getNext() {
    19.         return next;
    20.     }
    22.     public void setNext(Node<T> next) {
    23.         this.next = next;
    24.     }
    25. }
    1. public class SingleLinkedList<T> {
    2.     private int size;
    3.     private Node<T> head;
    5.     /**
    6.      * 添加
    7.      * @param v
    8.      */
    9.     public void add(T v){
    10.         if(size>0){
    11.             Node<T> node=new Node<>(v,null);
    12.             Node lastNode = getLastNode();
    13.             if(lastNode!=null){
    14.                 lastNode.setNext(node);
    15.                 size++;
    16.             }
    17.         }else {
    18.             if(head==null){
    19.                 head=new Node<>(v,null);
    20.             }else {
    21.                 head.setData(v);
    22.             }
    23.             size++;
    24.         }
    25.     }
    26.     public SingleLinkedList(){
    27.         size=0;
    28.         head=new Node<>(null,null);
    29.     }
    30.     /**
    31.      * 具体位置添加
    32.      * @param position
    33.      * @param v
    34.      */
    35.     public void insert(int position, T v){
    36.         if(position>=0 && position<size){
    37.             Node insertNode=new Node(v,null);
    38.             Node node=head;
    39.             Node pre=null;
    40.             if(position==0){
    41.                 insertNode.setNext(head);
    42.                 head=insertNode;
    43.                 size++;
    44.             }else {
    45.                 for(int x=0;x<position;x++){
    46.                     pre=node;
    47.                     node=node.getNext();
    48.                 }
    49.                 pre.setNext(insertNode);
    50.                 insertNode.setNext(node);
    51.                 size++;
    52.             }
    54.         }
    55.     }
    57.     /**
    58.      * 删除指定位置
    59.      * @param position
    60.      * @return
    61.      */
    62.     public T remove(int position)
    63.     {
    64.         if(position>=0 && position<size){
    65.             Node<T> node=head;
    66.             Node<T> pre=null;
    67.             Node<T> next=null;
    68.             T value=null;
    69.             if(position==0){
    70.                value= node.getData();
    71.                 node= node.getNext();
    72.               head.setNext(null);
    73.               head.setData(null);
    74.               head=node;
    75.               size--;
    76.             }else {
    77.                 for(int x=0;x<position;x++){
    78.                     //找到删除的节点
    79.                     pre=node;//当前要删除的上个节点
    80.                     node=node.getNext();//当前节点
    81.                     next=node.getNext();//当前需要删除的下个节点
    82.                 }
    83.                 value= (T) node.getData();
    84.                 node.setNext(null);
    85.                 node.setData(null);
    86.                 node=null;
    87.                 pre.setNext(next);
    88.                 size--;
    89.             }
    90.             return value;
    91.         }
    92.         return null;
    93.     }
    96.     /**
    97.      * 获取指定位置节点
    98.      * @param position
    99.      * @return
    100.      */
    101.     public Node getNode(int position){
    102.         if(position>=0 && position<size){
    103.             Node node=head;
    104.             for(int x=0;x<position;x++){
    105.                 node=node.getNext();
    106.             }
    107.             return node;
    108.         }else {
    109.             return null;
    110.         }
    111.     }
    113.     public Node getHead(){
    114.         return head;
    115.     }
    116.     /**
    117.      * 获取最后一个节点
    118.      * @return
    119.      */
    120.     public Node getLastNode(){
    121.         Node node=head;
    122.         while (node !=null && node.getNext()!=null){
    123.             node= node.getNext();
    124.         }
    125.             return node;
    126.         }
    128.     /**
    129.      * 清空
    130.      */
    131.     public void clear(){
    132.         for (int x=0;x<size;x++){
    133.             Node next=head.getNext();
    134.             head.setNext(null);
    135.             head.setData(null);
    136.             head= next;
    137.         }
    138.         size=0;
    139.     }
    141.     /**
    142.      * 查看第一个元素的数据
    143.      * @return
    144.      */
    145.     public T peek(){
    146.         if(size>0 && head!=null){
    147.             return head.getData();
    148.         }
    149.         return null;
    150.     }
    155.     /**
    156.      * 反转打印
    157.      */
    158.    public Node reversal(){
    159.        if (head == null){
    160.            return head;
    161.        }
    162.        Node node=head;
    163.        Node pre=null;
    164.        Node cur=node;
    165.        Node next=node.getNext();
    167.        //1->2->3->4->5
    168.        while (next!=null){
    169.          next=cur.getNext();//记录当前节点的下一个节点
    170.          cur.setNext(pre);//将当前节点的下一个节点指向当前节点的上一个节点//交换位置
    171.          pre=cur;//前一个节点后移到当前节点
    172.          cur=next;//当前节点设置成后一个节点
    173.        }
    174.        return pre;
    175.    }
    177.     /**
    178.      * 正序打印
    179.      */
    180.    public void print(Node n){
    181.        Node<T> node=n;
    182.        while (node!=null){
    183.            String data = (String) node.getData();
    184.            System.out.println("data:"+data);
    185.            node=node.getNext();
    186.        }
    187.    }
    189.    public boolean isEmpty(){
    190.        if(size==0 ){
    191.            return true;
    192.        }
    193.        return false;
    194.    }
    196.    public int getSize(){
    197.        return size;
    198.    }
    199. }

    双链表实现及反转

    1. public class DoublyLinkedList<V> {
    3.     private  Node<V> first;
    4.     private Node<V> last;
    5.     private int size;
    6.     public static class Node<V>{
    7.         V data;
    8.         Node<V> pre;
    9.         Node<V> next;
    11.         public Node(V data, Node<V> pre, Node<V> next) {
    12.             this.data = data;
    13.             this.pre = pre;
    14.             this.next = next;
    15.         }
    17.         public Node<V> getPre() {
    18.             return pre;
    19.         }
    21.         public void setPre(Node<V> pre) {
    22.             this.pre = pre;
    23.         }
    25.         public Node<V> getNext() {
    26.             return next;
    27.         }
    29.         public void setNext(Node<V> next) {
    30.             this.next = next;
    31.         }
    33.         public V getData() {
    34.             return data;
    35.         }
    37.         public void setData(V data) {
    38.             this.data = data;
    39.         }
    40.     }
    44.     public void add(V e){
    45.       Node<V> l=last;
    46.       Node<V> newNode=new Node<>(e,l,null);
    47.       last=newNode;
    48.       if(l==null){
    49.           first=newNode;
    50.       }else {
    51.           l.next = newNode;
    52.       }
    53.       size++;
    54.     }
    56.     /**
    57.      * 反转
    58.      */
    59.     public Node<V> reversal(){
    60.         if(first!=null){
    61.             Node<V> node=first;
    62.             Node<V> pre=null;
    63.             Node<V> cur=node;
    64.             Node<V> next=cur.getNext();
    65.             while (next!=null){
    66.                 next=cur.getNext();
    67.                 cur.setNext(pre);
    68.                 cur.setPre(next);
    69.                 pre=cur;
    70.                 cur=next;
    71.             }
    72.             return pre;
    73.         }
    74.         return null;
    75.     }
    77.     /**
    78.      * 具体位置添加
    79.      * @param position
    80.      * @param v
    81.      */
    82.     public void insert(int position, V v){
    83.         if(position>=0 && position<size){
    84.             Node pre=null;
    85.             if(position==0){
    86. //                Node node=first;
    87.                 Node insertNode=new Node(v,null,first);
    88.                 first.setPre(insertNode);
    89.                 first=insertNode;
    90.                 size++;
    91.             }else {
    92.                 Node insertNode=new Node(v,null,null);
    93.                 Node node=first;
    94.                 for(int x=0;x<position;x++){
    95.                     pre=node;
    96.                     node=node.getNext();
    97.                 }
    98.                 pre.setNext(insertNode);
    99.                 insertNode.setPre(pre);
    100.                 insertNode.setNext(node);
    101.                 node.setPre(insertNode);
    102.                 size++;
    103.             }
    105.         }
    106.     }
    108.     /**
    109.      * 删除指定位置
    110.      * @param position
    111.      * @return
    112.      */
    113.     public V remove(int position)
    114.     {
    115.         if(position>=0 && position<size){
    116.            Node<V> node=first;
    117.            Node<V> pre=null;
    118.            Node<V> next=null;
    119.             V value=null;
    120.             if(position==0){
    121.                 value= node.getData();
    122.                 node= node.getNext();
    123.                 first.setNext(null);
    124.                 first.setData(null);
    125.                 first=node;
    126.                 size--;
    127.             }else {
    128.                 for(int x=0;x<position;x++){
    129.                     //找到删除的节点
    130.                     pre=node;//当前要删除的上个节点
    131.                     node=node.getNext();//当前节点
    132.                     next=node.getNext();//当前需要删除的下个节点
    133.                 }
    134.                 value= (V) node.getData();
    135.                 node.setNext(null);
    136.                 node.setData(null);
    137.                 node.setPre(null);
    138.                 node=null;
    139.                 pre.setNext(next);
    140.                 next.setPre(pre);
    141.                 size--;
    142.             }
    143.             return value;
    144.         }
    145.         return null;
    146.     }
    151.     /**
    152.      * 获取指定位置节点
    153.      * @param position
    154.      * @return
    155.      */
    156.     public Node<V> getNode(int position){
    157.         if(position>=0 && position<size){
    158.            Node<V> node=first;
    159.             for(int x=0;x<position;x++){
    160.                 node=node.getNext();
    161.             }
    162.             return node;
    163.         }else {
    164.             return null;
    165.         }
    166.     }
    168.     public boolean isEmpty(){
    169.         if(size==0 ){
    170.             return true;
    171.         }
    172.         return false;
    173.     }
    175.     public int getSize(){
    176.         return size;
    177.     }
    179.     /**
    180.      * 查看第一个元素的数据
    181.      * @return
    182.      */
    183.     public V peek(){
    184.         if(size>0 && first!=null){
    185.             return first.getData();
    186.         }
    187.         return null;
    188.     }
    190.     /**
    191.      * 清空
    192.      *
    193.      */
    194.     public void clear(){
    195.         while (first!=null){
    196.                 Node<V> next=first.getNext();
    197.                 first.setNext(null);
    198.                 first.setData(null);
    199.                 first.setPre(null);
    200.                 first= next;
    201.         }
    202.         size=0;
    203.     }
    205.     public void print(){
    206.         Node<V> node=first;
    207.         while (node !=null){
    208.             System.out.println("data="+node.getData());
    209.             node=node.getNext();
    210.         }
    211.     }
    213.     public void print2(Node<V> node){
    214.         while (node !=null){
    215.             System.out.println("data2="+node.getData());
    216.             node=node.getNext();
    217.         }
    218.     }
    221. }