Java全面讲解顺序表与链表的使用（java链表的基本操作）

目录线性表顺序表链表小结

线性表

线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见 的线性表：顺序表、链表、栈、队列、字符串 ... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构（内存上）上并不一定是连续的，线性表在物理上存储时，通常以数组（在物理上是连续的）和链式结构（在物理上不连续）的形式存储。

顺序表

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。（可以说顺序表就相当于一个数组）

那么问题来了，为什么不直接使用数组，而要把数组放在类当中，然后再对数组进行操作？ 因为数组没有面向对象，把数组放进类当中，可通过对象对它进行操作。

听着概念有点模糊，接下来通过模拟顺序表的接口实现来认识一下顺序表：

用Arraylist来模拟实现顺序表ArrayList的接口实现：

Arraylist:

public class Arraylist{

public int[] arr;

public int useSize;//数组有效个数

public Arraylist() {

this.arr = new int[10];//假设数组长度为10

}

//打印顺序表

public void display() {

for (int i = 0; i < this.useSize; i++) {

System.out.print(this.arr[i] + " ");

}

System.out.println();

}

public boolean isFull() {

return this.arr.length == this.useSize;

}

// 在 pos 位置新增元素

public void add(int pos, int date) {

if (pos < 0 || pos > useSize) {

System.out.println("pos位置不合法"+" ");

return;

}

if (isFull()) {

this.arr = Arrays.copyOf(this.arr, 2 * this.arr.length);

}

for (int i = this.useSize - 1; i >= pos; i--) {

this.arr[i + 1] = this.arr[i];

}

this.arr[pos] = date;

this.useSize++;

}

// 判定是否包含某个元素

public boolean contains(int toFind) {

for (int i = 0; i < this.useSize; i++) {

if (arr[i] == toFind) {

return true;

}

}

return false;

}

// 查找某个元素对应的位置

public int search(int toFind) {

for (int i = 0; i < this.useSize; i++) {

if (arr[i] == toFind) {

return i;

}

}

return -1;

}

// 获取 pos 位置的元素

public int getPos(int pos) {

if (pos < 0 || pos >=useSize){

System.out.println("pos位置不合法"+" ");

return -1;//万一顺序表中有-1这个元素怎么办，后期说

}

if(isEmpty()){

System.out.print("顺序表为空");

return -1;

}

for (int i = 0; i < this.useSize; i++) {

if (i == pos) {

return this.arr[i];

}

}

return -1;

}

public boolean isEmpty(){

return this.useSize==0;

}

// 给 pos 位置的元素设为 value

public void setPos(int pos, int value) {

if (pos < 0 || pos >=useSize){

System.out.print("pos位置不合法"+" ");

return;

}

if(isEmphttp://ty()){

System.out.println("顺序表为空");

return;

}

this.arr[pos] = value;

}

//删除第一次出现的关键字key

public void remove(int toRemove){

if(isEmpty()) {//判断顺序表是否为空

System.out.println("顺序表为空");

}

int x=search(toRemove);

if(x==-1){

System.out.println("没有你要删除的数字");

return;

}

for (int j = x; j<=this.useSize-1; j++) {

this.arr[j]=this.arr[j+1];

}

this.useSize--;

}

//清空顺序表

public void clear() {

this.usedSize = 0;

}

}

在pos位置新增元素：

判断是否包含某个元素：

查找pos位置：

在pos位置上给值value

删除第一次出现的关键字key

链表

链表是一种 物理存储结构(内存）上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。 实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：

单向、双向

带头、不带头

循环、非循环

接下来主要讲两种：单向不带头非循环、双向不带头非循环

链表接口的模拟实现（ 单向不带头非循环）： 链表是由一个一个节点组成，单向不带头非循环链表每个节点有两个域，一个是数据域，用来存放数据，另一个是存放下一个节点的地址。

class ListNode{//创建节点,链表是由一个一个节点组成，每个节点有两个域组成，数据域和下一个节点地址组成

public int val;

public ListNode next;//没有初始化默认为null

public ListNode(int val){

this.val=val;

}

}

//模拟实现单向不带头非循环链表的接口实现，用MyLinkedList模拟实现LinkedList

public class MyLinkedList {

public ListNode head;//创建头节点

public void createList() {

ListNode listNode1 = new ListNode(12);

ListNode listNode2 = new ListNode(88);

ListNode listNode3 = new ListNode(36);

listNode1.next = listNode2;

listNode2.next = listNode3;

this.head = listNode1;//头节点为第一个节点地址

}

public void display() {

ListNode cur;

cur = this.head;

while (cur != null) {

System.out.print(cur.val + " ");

cur = cur.next;

}

System.out.println();

}

//头插法

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);

ListNode cur = http://this.head;

if (cur == null) {

this.head = node;

} else {

while (cur.next != null) {

cur = cur.next;

}

cur.next = node;

}

}

//找到index-1下标位置

public ListNode findIndex(int index) {

ListNode cur = this.head;

while (index - 1 != 0) {

cur = cur.next;

index--;

}

return cur;

}

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

public void addIndex(int index, int data) {

if(index<0||index>size()){

System.out.println("输入位置不合法");

return;

}

if(index==0){//头插

this.addFirst(data);

return;

}

if(index==size()){//尾插

this.addLast(data);

return;

}

ListNode cur = findIndex(index);

ListNode node = new ListNode(data);

node.next = cur.next;

cur.next = node;

}

public boolean contains(int key) {

return false;

}

public ListNode findremove(int key){

ListNode cur=this.head.next;

while(cur!=null) {

if (cur.next.val == key) {

return cur;

} else {

cur=cur.next;

}

}

return null;

}

//删除第一次出现关键字为key的节点

public void remove(int key) {

if (this.head == null) {

System.out.println("链表为空");

return;

}

if (this.head.val == key) {

this.head = this.head.next;

return;

}

ListNode cur = findremove(key);//找到关键字上一个节点所在位置，并返回该节点

if (cur == null) {

System.out.println("没找到关键字");

return;

}

ListNode del=cur.next;

cur.next=del.next;

return;

}

//删除所有值为key的节点

public ListNode removeAllKey(int key) {

if(this.head==null){

return null;

}

ListNode per=this.head;

ListNode cur=this.head.next;

while(cur!=null){

if(cur.val==key){

per.next=cur.next;

cur=cur.next;

}

else{

per=cur;

cur=cur.next;

}

}

if(this.head.val==key){

this.head=this.head.next;

}

return this.head;

}

//得到单链表的长度

public int size() {

ListNode cur=this.head;

int count=0;

while (cur!=null){

count++;

cur=cur.next;

}

return count;

}

//清除链表

public void clear() {

//this.head=null;//简单粗暴写法，当一个节点没有被指向时，就没意义了

//遍历

while(this.head!=null){

ListNode curNext=this.head.next;

this.head.next=null;

this.head=curNext;

}

}

}

创建节点：

以上说的链表是指单向不带头非循环链表！！！

初始化链表：

打印链表：

头插法：

尾插法：

任意位置插入一个数据：

删除关键字key所在节点位置：

删除所有值为key的节点：

双向不带头非循环：

这种链表至少有三个域组成，一个是数据域，一个是存放上一个节点的位置，一个存放下一个节点的位置，双向比单向的好处就体现出来了，双向链表只要知道当前节点位置，就可以对链表进行增删查改，而单相链表还需要知道当前节点的上一个节点。

接口模拟实现：

//双向不带头非循环

//创建节点

class ListNode{

int val;

ListNode prev;//前一个节点地址

ListNode next;//下一个节点地址

public ListNode(int val){

this.val=val;

}

}

public class myLinkedList {

public ListNode head;//头节点

public ListNode last;//尾节点

//得到双向链表长度

public int size() {

int count = 0;

ListNode cur = this.head;

while (cur != null) {

count++;

cur = cur.next;

}

return count;//如果链表为空。返回0，所以这里可再单独判断也可不单独判断

}

//打印双向链表

public void display() {

ListNode cur = this.head;

while (cur != null) {

System.out.print(cur.val + " ");

cur = cur.next;

}

System.out.println();

}

//查找是否包含关键字在链表中

public boolean contain(int key) {

if (this.head == null) {

return false;

}

ListNode cur = this.head;

while (cur != null) {

if (cur.val == key) {

return true;

}

cur = cur.next;

}

return false;

}

//删除第一次出现的关键字

public void remove(int key) {

ListNode cur = this.head;

while (cur != null) {

if (cur.val == key) {

if (cur == head) {//第一种：关键字是在头节点

this.head = this.head.next;

if (this.head != null) {

head.prev = null;

} else {//如果链表为空1情况下，要保证最后一个节点也要为空

this.last = null;

}

} else {//第二种情况：关键字在中间或者结尾

cur.prev.next = cur.next;

if (cur.next != null) {//中间

cur.next.prev = cur.prev;

} else {

last = cur.prev;//结尾

xIVefT }

}

return;

}

cur=cur.next;

}

}

//删除所有值为key的节点

public void removeAllkey(int key) {

ListNode cur = this.head;

while (cur != null) {

if (cur.val == key) {

if (cur == head) {//第一种：关键字是在头节点

this.head = cur.next;

if (this.head != null) {

cur.next.prev = null;

} else {//如果链表为空1情况下，要保证最后一个节点也要为空

this.last = null;

}

} else {//第二种情况：关键字在中间或者结尾

cur.prev.next = cur.next;

if (cur.next!=null) {//中间

cur.next.prev = cur.prev;

}

last = cur.prev;//结尾

}

}

cur=cur.next;

}

}

//头插法

public void addFirst(int data) {

ListNode node = new ListNode(data);

if (this.head == null) {

this.head = node;

this.last = node;

}

else {

node.next = this.head;

this.head.prev = node;

this.head = node;

}

}

//尾插法

public void addLast(int data){

ListNode node=new ListNode(data);

if(this.head==null) {

this.head = node;

this.last = node;

}

this.last.next=node;

node.prev=this.last;

this.last=node;

}

//任意位置插入，第一个数据节点下标为0

public ListNode search(int index){//寻找插入的位置

ListNode cur=this.head;

while(index!=0){

cur=cur.next;

index--;

}

return cur;

}

public void addIndex(int index,int data){

ListNode node=new ListNode(data);

if(index<0||index>size()){

System.out.println("坐标违法");

return;

}

if(index==0){

addFirst(data);

return;

}

if(index==size()){

addLast(data);

return;

}

ListNode cur=search(index);

node.next=cur.prev.next;

cur.prev.next=node;

node.prev=cur.prev;

cur.prev=node;

return;

}

//清除链表

public void clear(){

while(this.head!=null){

ListNode curNext=this.head.next;

this.head.prev=null;

this.head.next=null;

this.head=curNext;

}

xIVefTlast=null;

}

}

查找是否包含关键字在链表中：

删除第一次出现的关键字：

删除所有值为key的节点：

头插法：

尾插法：

任意位置插入，第一个数据节点下标为0：

小结

在这里，我们讲了顺序表也讲了链表，那么他们有什么区别呢？

在组织上：

1、顺序表底层是一个数组，他是一个逻辑上和物理上都是连续的

2、链表是一个由若干节点组成的一个数据结构，逻辑上是连续的但是在物理上[内存上]是不连续的。

在操作上：

1、顺序表适合，查找相关的操作，因为，可以使用下标，直接获取到某个位置的元素。

2、链表适合于,频繁的插入和删除操作。此时不需要像顺序表一样,移动元素。链表的插入只需要修改指向即可。

3、顺序表还有不好的地方，就是你需要看满不满，满了要扩容，扩容了之后，不一定都能放完。所以，他的空间上的利用率不高。

以上就是我对顺序表和链表的一些理解，如果有什么不对的地方，欢迎各位提出来！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。