数据结构及算法之链表讲解

短命女 2024-04-18 23:19 84阅读 0赞

1，普通实现方式

<table> 
 <tbody> 
  <tr> 
   <td> <pre><code>package com.dream21th.algorithmicdatastructure.linkedlist;

/**
 * @Auther: hp
 * @Date: 2019/9/13 16:07
 * @Description:
 */
public class LinkList&lt;E&gt; {

private class Node{

public E e;

public Node next;

public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

public Node(E e){
            this(e,null);
        }

public Node(){
            this(null,null);
        }

@Override
        public String toString() {
            return e.toString();
        }
    }

private Node head;
    private int size;

public LinkList() {
        this.head=null;
        size=0;
    }

public int getSize(){
        return size;
    }

public boolean isEmpty(){
        return size==0;
    }

public void addFirst(E e){
       /* Node node = new Node(e);
        node.next=head;
        head=node;*/
        head = new Node(e, head);
        size++;
    }

public void add(int index,E e){
        if(index&lt;0 || index&gt;size){
            throw new IllegalArgumentException("index is illegal");
        }

if(index==0){
            addFirst(e);
        }else {

Node prev=head;
            for(int i=0;i&lt;index-1;i++){
                prev=prev.next;
            }

prev.next=new Node(e,prev.next);
        }
    }

public void addLast(E e){
        add(size,e);
    }
}
</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

2，带虚拟头节点实现方式

<table> 
 <tbody> 
  <tr> 
   <td> <pre><code>package com.dream21th.algorithmicdatastructure.linkedlist;

/**
 * @Auther: hp
 * @Date: 2019/9/13 16:07
 * @Description:
 */
public class LinkedList&lt;E&gt; {

private class Node{

public E e;

public Node next;

public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

public Node(E e){
            this(e,null);
        }

public Node(){
            this(null,null);
        }

@Override
        public String toString() {
            return e.toString();
        }
    }

/**
     * 虚拟头节点
     */
    private Node dummyHead;
    private int size;

public LinkedList() {
        this.dummyHead=new Node(null,null);
        size=0;
    }

public int getSize(){
        return size;
    }

public boolean isEmpty(){
        return size==0;
    }

public void add(int index,E e){
        if(index&lt;0 || index&gt;size){
            throw new IllegalArgumentException("index is illegal");
        }

Node prev=dummyHead;
        for(int i=0;i&lt;index;i++){
            prev=prev.next;
        }

prev.next=new Node(e,prev.next);
        size++;

}

public void addFirst(E e){
      add(0,e);
    }
    public void addLast(E e){
        add(size,e);
    }

public E get(int index){
        if(index&lt;0 || index&gt;=size){
            throw new IllegalArgumentException("index is illegal");
        }
        Node cur=dummyHead.next;

for(int i=0;i&lt;index;i++){
            cur=cur.next;
        }
        return cur.e;
    }

public E getFirst(){
        return get(0);
    }

public E getLast(){
        return get(size-1);
    }

public boolean contains(E e){
        for(Node cur=dummyHead.next;cur!=null;cur=cur.next){
            if(cur.e.equals(e)){
                return true;
            }
        }
        return false;
    }

public void set(int index,E e){
        if(index&lt;0 || index&gt;=size){
            throw new IllegalArgumentException("index is illegal");
        }
        Node cur=dummyHead.next;

for(int i=0;i&lt;index;i++){
            cur=cur.next;
        }
        cur.e=e;
    }

public E remove(int index){
        if(index&lt;0 || index&gt;=size){
            throw new IllegalArgumentException("index is illegal");
        }
        Node prev=dummyHead;
        for(int i=0;i&lt;index;i++){
            prev=prev.next;
        }
        Node currentNode = prev.next;
        prev.next=currentNode.next;
        currentNode.next=null;
        size--;
        return currentNode.e;
    }

public E removeFirst(){
        return remove(0);
    }

public E removeLast(){
        return remove(size-1);
    }
    @Override
    public String toString() {
        StringBuilder builder=new StringBuilder();
        Node cur = dummyHead.next;
        while (cur!=null){
            builder.append(cur+"-&gt;");
            cur=cur.next;
        }
        builder.append("NULL");
        return builder.toString();
    }
}
</code></pre> </td> 
  </tr> 
 </tbody> 
</table>