【恋上数据结构】 链表(手写LinkedList+练习)

Gitee地址

• • linkedList(链表)
  • • 节点类(Node)
    • 接口设计
    • 手写linkedList
    • 练习
    • • 1.删除链表中的节点
      • 2.反转链表

动态数组有个明显的缺点:
动态数组可能会造成内存空间的大量浪费

能否用到多少内存就申请多少内存呢？链表就可以办到这一点，链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。

    private static class Node{
        
        E element;

        
        Node next;

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

由于链表与动态数组可以抽象出共同的方法，所以我们可以实现接口来优化代码。

抽象接口之后创建对象的方法变为：

List list = new linkedList();

接口设计为：

package 链式结构;

public interface List {

	static final int ELEMENT_NOT_FOUND = -1;
	
	void clear();

	
	int size();

	
	boolean isEmpty();

	
	boolean contains(E element);

	
	void add(E element);

	
	E get(int index);

	
	E set(int index, E element);

	
	void add(int index, E element);

	
	E remove(int index);

	
	int indexOf(E element);
}

linkedList

package 链式结构.linkedlist;

import org.w3c.dom.Node;
import 链式结构.List;



public class linkedList implements List {

    
    
    private int size;
    
    private Node first;



    
    
    public linkedList(){
    }


    

    
    @Override
    public void clear() {
        size = 0;
        first = null;
    }

    @Override
    public int size() {
        return size;
    }

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

    @Override
    public boolean contains(Object element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    @Override
    public void add(Object element) {
        add(size,element);
    }

    @Override
    public Object get(int index) {
        Node node = node(index);
        return node.element;
    }

    @Override
    public Object set(int index, Object element) {
        Node node = node(index);
        E old = node.element;;
        node.element = (E) element;
        return old;
    }

    
    @Override
    public void add(int index, Object element) {
        if (index == 0){
            first = new Node<>(element, first);
        }else {
            //前一个节点
            Node preNode = node(index - 1);
            //新节点
            Node node = (Node) new Node(element, preNode.next);
            //前一个节点指向新的
            preNode.next = node;
        }
        //长度增加
        size++;
    }
    private Node node(int index){
        rangeCheck(index);
        Node node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    
    @Override
    public Object remove(int index) {
        rangeCheck(index);
        Node node = first;
        if (index == 0){
         first = first.next;
        }else {
            Node prevNode = node(index - 1);
            prevNode.next = prevNode.next.next;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(Object element) {
        if (element == null){
            Node node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null){return i;}
                node = node.next;
            }
        }else {
            Node node = first;
            for (int i = 0; i < size; i++){
                if (element.equals(node.element)){return i;}
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("size=").append(size).append(",[");
        Node node = first;
        for (int i = 0; i < size; i++) {
            if(i != 0){
                stringBuilder.append(",");
            }
            stringBuilder.append(node.element);
            node = node.next;
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    

    
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index"+index+",Size:"+size);
    }
    
    private void rangeCheck(int index){
        if (index < 0 || index >= size){
            outOfBounds(index);
        }
    }
    
    private void rangeCheckForAdd(int index){
        if (index < 0 || index > size){
            outOfBounds(index);
        }
    }


    

    
    private static class Node{
        
        E element;

        
        Node next;

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

}

分析：

当前节点的值 = .next的值

当前节点的next= .next.next;

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

递归解法

class Solution {
    public ListNode reverseList(ListNode head) {
        //返回条件
        if(head == null || head.next == null){return head;}
        
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){return head;}
        ListNode newHead = null;
        while(head != null){
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}