Java实现链表_java链表

在Java编程中，顺序表是一种基础且重要的数据结构。它通常用来表示线性结构数据，如数组等。通过使用顺序表，我们可以轻松管理和操作大量的数据，并实现各种算法和功能。

---

一、认识List

List是一个接口，继承自Collection， Collection同样是接口。

List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删 改查以及变量等操作。

二、常见的Collection中有那些方法？

这可是面试题常问的哦！

具体如下：

三、线性表

线性表（底层就是数组）：如顺序表、栈、队列等

逻辑上是线性结构，物理结构上不一定是连续的，通常以数组和链式结构的形式存储

• 方法空白代码给你们放出来了，小伙伴们可以自己动手试试哦

public class SeqList {
private int[] array;
private int size;
// 默认构造方法
SeqList(){ }
// 将顺序表的底层容量设置为initcapacity
SeqList(int initcapacity){ }
// 新增元素,默认在数组最后新增
public void add(int data) { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 查找某个元素对应的位置
public int indexOf(int toFind) { return -1; }
// 获取 pos 位置的元素
public int get(int pos) { return -1; }
// 给 pos 位置的元素设为 value
public void set(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display() { }
}

实现线性表：

• 遍历单链表：

//遍历单链表
    public void show() {
        //这里不是定义了一个节点 这里只是一个引用
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
 
    public void show(ListNode newHead) {
        //这里不是定义了一个节点 这里只是一个引用
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

 

• 链表的长度：

//得到单链表的长度 --》 链表中节点的个数
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

 

•  查找是否包含关键字key是否在单链表当中：

 //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            //如果val值 是引用类型  那么这里得用equals来进行比较！！！
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

 

• 头插法&&尾插法：

 //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
 
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        //cur 指向的节点就是尾巴节点
        cur.next = node;
    }

 

•  任意位置插入,第一个数据节点为0号下标

//任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        int len = size();
        //0、判断index位置的合法性
        if(index < 0 || index > len) {
            throw new IndexOutOfBounds("任意位置插入数据的时候，index位置不合法: "+index);
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == len) {
            addLast(data);
            return;
        }
        //1、先找到index-1位置的节点
        ListNode cur = findIndex(index);
        //2、进行插入
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

•  删除所有值为key的节点

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null) {
            return;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while (cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val ==  key) {
            head = head.next;
        }
    }

•     完整代码

• import java.util.List;
  import java.util.Stack;
   
   
  public class MySingleList {
      static class ListNode {
          public int val;
          public ListNode next;
   
          public ListNode(int val) {
              this.val = val;
          }
      }
   
      public ListNode head;//永远指向我的头节点
   
      //遍历单链表
      public void show() {
          //这里不是定义了一个节点 这里只是一个引用
          ListNode cur = head;
          while (cur != null) {
              System.out.print(cur.val+" ");
              cur = cur.next;
          }
          System.out.println();
      }
   
      public void show(ListNode newHead) {
          //这里不是定义了一个节点 这里只是一个引用
          ListNode cur = newHead;
          while (cur != null) {
              System.out.print(cur.val+" ");
              cur = cur.next;
          }
          System.out.println();
      }
   
      //得到单链表的长度 --》 链表中节点的个数
      public int size(){
          int count = 0;
          ListNode cur = head;
          while (cur != null) {
              count++;
              cur = cur.next;
          }
          return count;
      }
   
      //查找是否包含关键字key是否在单链表当中
      public boolean contains(int key){
          ListNode cur = head;
          while (cur != null) {
              //如果val值 是引用类型  那么这里得用equals来进行比较！！！
              if(cur.val == key) {
                  return true;
              }
              cur = cur.next;
          }
          return false;
      }
   
      //头插法
      public void addFirst(int data){
          ListNode node = new ListNode(data);
          node.next = head;
          head = node;
      }
   
      //尾插法
      public void addLast(int data){
          ListNode node = new ListNode(data);
          if(head == null) {
              head = node;
              return;
          }
          ListNode cur = head;
          while (cur.next != null) {
              cur = cur.next;
          }
          //cur 指向的节点就是尾巴节点
          cur.next = node;
      }
   
      //任意位置插入,第一个数据节点为0号下标
      public void addIndex(int index,int data){
          int len = size();
          //0、判断index位置的合法性
          if(index < 0 || index > len) {
              throw new IndexOutOfBounds("任意位置插入数据的时候，index位置不合法: "+index);
          }
          if(index == 0) {
              addFirst(data);
              return;
          }
          if(index == len) {
              addLast(data);
              return;
          }
          //1、先找到index-1位置的节点
          ListNode cur = findIndex(index);
          //2、进行插入
          ListNode node = new ListNode(data);
          node.next = cur.next;
          cur.next = node;
      }
   
   
      //删除所有值为key的节点
      public void removeAllKey(int key){
          if(head == null) {
              return;
          }
          ListNode cur = head.next;
          ListNode prev = head;
          while (cur != null) {
              if(cur.val == key) {
                  prev.next = cur.next;
                  cur = cur.next;
              }else {
                  prev = cur;
                  cur = cur.next;
              }
          }
          if(head.val ==  key) {
              head = head.next;
          }
      }
   
      public void clear() {
          //this.head = null;
          while (head != null) {
              ListNode headNext = head.next;
              head.next = null;
              head = headNext;
          }
      }
   
   
   
  

---

总结

以上就是今天要讲的内容，本文仅仅简单介绍了链表的基本知识与链表的实现，链表是数据结构的开门红，好好理解，慢慢消化，多打代码，坚持住，别放弃。