02线性结构——线性表：数组和链表

喜欢ヅ旅行 2023-07-01 08:36 34阅读 0赞

**目录**

一、线性表

二、数组

2.1、动态数组

简单动态数组实现：

三、链表

简单单向链表实现：

双向链表

循环链表

--------------------

# 一、线性表 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 2][]

package com.turingschool.demo.ds;
    
    public interface List<E> {
    	
    	//返回线性表的大小
    	public int getSize();
    
    	//判断线性表中是否为空
    	public boolean isEmpty();
    
    	//判断线性表中是否包含元素o
    	boolean contains(E o);
    	
    	//在线性表中查找元素o，若成功找到，返回其位置index；否则，返回-1
    	public int indexOf(E e);
    
    	//获取线性表中 位置为index的元素
    	public E get(int index);
    
    	//将线性表中 位置为index的元素设置为e
    	public void set(int index, E e);
    
    	//在线性表中位置为index处添加元素e
    	public void add(int index, E e);
    
    	//删除并返回线性表中位置为index的元素
    	public E remove(int index);
    }

# 二、数组 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 3][]

## 2.1、动态数组 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 4][]

### 简单动态数组实现： ###

package com.turingschool.demo.ds;
    
    import java.util.Arrays;
    
    public class ArrayList<E> implements List<E>{
    	
    	private static final int DEFAULT_CAPACITY = 10;
    	
    	private E[] data;
    	private int size;
    	
    	public ArrayList(int capacity) {
    		this.size = 0;
    		data = (E[]) new Object[capacity];
    	}
    	
    	public ArrayList() {
    		this(DEFAULT_CAPACITY);
    	}
    
    	//O(1)
    	@Override
    	public int getSize() {
     		return size;
    	}
    
    	//O(1)
    	@Override
    	public boolean isEmpty() {
     		return size == 0;
    	}
    
    	//O(n)
    	@Override
    	public boolean contains(E o) {
    		for(int i=0; i<size; i++) {
    			if(data[i].equals(o))
    				return true;
    		}
    		
    		return false;
    	}
    
    	//O(n)
    	@Override
    	public int indexOf(E e) {
    		for(int i=0; i<size; i++) {
    			if(data[i].equals(e))
    				return i;
    		}
    		
     		return -1;
    	}
    
    	//O(1)
    	@Override
    	public E get(int index) {
    		if(index < 0 || index >= size)
    			throw new IllegalArgumentException("数组小标越界...");
    		
    		return data[index];
    	}
    
    	//O(1)
    	@Override
    	public void set(int index, E e) {
    		if(index < 0 || index >= size)
    			throw new IllegalArgumentException("数组小标越界...");
    		
            data[index] = e;		
    	}
    
    	//O(n)
    	@Override
    	public void add(int index, E e) {
    		if(index < 0 || index > size) {
    			throw new IllegalArgumentException("数组小标越界...");
    		}
    		
    		if(size == data.length) {
    			grow(2*data.length);
    		}
    		
    		for(int i=size-1; i>=index; i--) {
    			data[i+1] = data[i];
    		}
    		
    		data[index] = e;
    		
    		size++;
    		
    	}
    	
    	//均摊时间复杂度 O(1)
    	public void addLast(E e) {
    		add(size, e);
    	}
    
    	//O(n)
    	@Override
    	public E remove(int index) {
    		if(index < 0 || index >= size) {
    			throw new IllegalArgumentException("数组小标越界...");
    		}
    		
    		E val = data[index];
    		
    		for(int i = index + 1; i<size; i++) {
    			data[i-1] = data[i];
    		}
    		
    		size--;
    		
    		data[size] = null;
    		
    		if(size < (data.length >> 1)) {
    			grow(data.length/2);
    		}
    		
    		return val;
     	}
    
    	private void grow(int newCapacity) {
    	/*	E[] newData = (E[]) new Object[newCapacity];
    		for(int i=0; i<data.length; i++)
    			newData[i] = data[i];
    		
    		data = newData;*/
    		data = Arrays.copyOf(data, newCapacity);
    	}
    	
    	public static void main(String[] args) {
    		List<Integer> list = new ArrayList<>();
    		
    		for(int i=0; i<100; i++)
    			list.add(i, i);
    		
    		for(int i=0; i<100; i++) {
    			System.out.println("The " + i + "th element is: " + list.get(i));
    		}
    		
    		for(int i=0; i<50; i+=8) {
    			list.remove(i);
    		}
    		
    		for(int i=0; i<list.getSize(); i++) {
    			System.out.println("After removing, the " + i + "th element is: " + list.get(i));
    		}
    		
    	}
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 6][]

LeetCode283题：给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。

class Solution {
        int tmp;
        public void moveZeroes(int[] nums) {
            if(nums == null || nums.length == 0){
                return;
            }
            int flag = 0;//从左到右不为0的下一个位置的标记。
            for(int i=0;i<nums.length;i++){
                if(nums[i] != 0){
                    if(i != flag){//如果当前不为0的角标不等于（从左到右不为0的下一个）标记位，则将当前值和标记位的值交换。
                        swap(nums,flag,i);
                    }
                    flag++;
                }
            }
            return; 
        }
    
        private void swap(int[] nums,int flag,int i){
            tmp = nums[flag];
            nums[flag] = nums[i];
            nums[i] = tmp;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 8][]

# 三、链表 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 9][]

### 简单单向链表实现： ###

package com.turingschool.demo.ds;
    
    public class LinkedList<E> implements List<E> {
    
    	private class Node {
    		private E data; //数据域
    		private Node next; //指针域，指向下一个Node
    		
    		public Node(E data, Node next) {
    			this.data = data;
    			this.next = next;
    		}
    		
    		public Node(E data) {
    			this(data, null);
    		}
    		
    		public String toString() {
    			return data.toString();
    		}
    	}
    	
    	
    	private Node head;
    	//private Node tail;
    	private int size;
    	
    	public LinkedList() {
    		head = null;
    		size = 0;
    	}
    	
    	
    	//O(1)
    	@Override
    	public int getSize() {
     		return size;
    	}
    
    	//O(1)
    	@Override
    	public boolean isEmpty() {
     		return size == 0;
    	}
    
    	//O(n)
    	@Override
    	public boolean contains(E o) {
    		Node p = head;
    		while(p != null) {
    			if(p.data.equals(o))
    				return true;
    			p = p.next;
    		}
     		return false;
    	}
    
    	//O(n)
    	@Override
    	public int indexOf(E e) {
    		
    		int result = -1;
    		Node p = head;
    		int i = 0;
    		while(p != null) {
    			if(p.data.equals(e))
    			{
    				result = i;
    				break;
    			}
     			p = p.next;
    			i++;
    		}
     		return result;
    	}
    
    	//O(n)
    	@Override
    	public E get(int index) {
    		if(index<0 || index >= size) {
    			throw new IllegalArgumentException("非法下标...");
    		}
    		
    		Node p = head;
    		for(int i=0; i<index; i++)
    			p = p.next;
    		
    		return p.data;
    	}
    
    	//O(n)
    	@Override
    	public void set(int index, E e) {
    		if(index<0 || index >= size) {
    			throw new IllegalArgumentException("非法下标...");
    		}
    		
    		Node p = head;
    		for(int i=0; i<index; i++)
    			p = p.next;
    		
    		 p.data = e;		
    	}
    
    	//O(n)
    	@Override
    	public void add(int index, E e) {
    		if(index < 0 || index > size) {
    			throw new IllegalArgumentException("下标越界.....");
    		}
    		
    		//插到链表头部
    		if(index == 0) {
    			addFirst(e);
    		}else if(index == size) {
    			addLast(e);
    		}else {
    			Node prev = head;
    			for(int i=0; i<index; i++) {
    				prev = prev.next;
    			}
    			
    			prev.next = new Node(e, prev.next);
    			
    			size++;
    		}
     		
    	}
    	
    	//O(1)
    	public void addFirst(E e) {
    		Node node = new Node(e, head);
    		head = node;
    		
    		size++;
    	}
    	
    	//O(n)
    	public void addLast(E e) {
    		Node node = new Node(e, null);
    		
    		//链表为空
    		if(head == null) {
    			head = node;
    		}else {
    			Node prev = head;
    			while(prev.next != null) {
    				prev = prev.next;
    			}
    			
    			prev.next = node;
    		}
    		
    		size++;
    	}
    
    	//O(n)
    	@Override
    	public E remove(int index) {
    		
    		if(index<0 || index >= size) {
    			throw new IllegalArgumentException("非法下标...");
    		}
    		
    		if(index == 0) {
    			return removeFirst();
    		}else if (index == size -1) {
    			return removeLast();
    		}else{
    			
    			Node prev = head;
    			for(int i=0; i<index-1; i++)
    				prev = prev.next;
    			
    			Node tmp = prev.next;
    			prev.next = tmp.next;
    			tmp.next = null;
    			size--;
    			
    			return tmp.data;
    					
    			
    		}
     	}
    	
    	//O(1)
    	public E removeFirst() {
    		if(head == null)
    			return null;
    		
    		E result = head.data;
    		head = head.next;
    		size--;
    		
    		return result;
    	}
    	
    	//O(n)
    	public E removeLast() {
    		if(head == null)
    			return null;
    		
    		E result;
    		
    		//链表只有一个节点
    		if(head.next == null) {
    			result = head.data;
    			head = null;
    		}else {
    			
    			Node prev = head;
    			while(prev.next.next != null)
    				prev = prev.next;
    			
    			result = prev.next.data;
    			prev.next = null;
    		}
    		
    		size--;
    		return result;
    
    	}
    	
    	public static void main(String[] args) {
    		List<Integer> list = new LinkedList<>();
    		
    		for(int i=0; i<10; i++)
    			list.add(i, i);
    		
    		for(int i=0; i<10; i++) {
    			System.out.println("The " + i + "th element is: " + list.get(i));
    		}
    		
    		list.remove(0);
    		
    		for(int i=0; i<list.getSize(); i++) {
    			System.out.println("After removing, the " + i + "th element is: " + list.get(i));
    		}
    		
    	}
    
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 10][]

### 双向链表 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 11][]

### 循环链表 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 12][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 13][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 14][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200120103854537.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200120103952407.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200120104047261.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020012011240846.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020012011304525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200120113151894.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200120113229133.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200120113331457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200120113429996.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200120113603246.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200120113703217.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/2020012011375212.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200120113927787.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200120113946757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200120114110755.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0d3htaW5n,size_16,color_FFFFFF,t_70