JAVA学*笔记 顺序表和链表

发布于:2021-05-11 23:49:44

顺序表和链表的优缺点:



特点:内存是连续的
缺点:
1.再插入元素的时候,最坏情况下时间复杂度是O(n)
2.不能做到随用随取
优点:
1.如果是用下标去访问元素,时间复杂度是O(1)


链表则与之相反;



顺序表及相关接口实现


package TestDome;

import java.util.Arrays;

public class MyArrayList {
public int[] elem;
public int useSize;
public MyArrayList(){
this.elem = new int[5];
}
public MyArrayList(int size) {
this.elem = new int[size];
}
public void display() {
for (int i = 0; i < useSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public void Resize() {
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
public boolean Isfull() {
if (this.useSize == this.elem.length) {
return true;
}
return false;
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
if (Isfull()) {
Resize();
}
if (pos < 0 || pos > this.useSize) {
System.out.println("pos不合法!");
return;
}
for (int i = useSize-1; i >= pos; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.useSize++;
}
public void add2(int date) {
this.elem[this.useSize] = date;
this.useSize++;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.useSize; i++) {
if (this.elem[i] == toFind) {
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int search(int toFind) {
int count = 0;
for (int i = 0; i < this.useSize; i++) {
if (this.elem[i] == toFind) {
return count;
}
count++;
}
return -1;
}
// 获取 pos 位置的元素
public int getPos(int pos) {
int count = 0;
for (int i = 0; i < this.useSize; i++) {
if (count == pos) {
return this.elem[i];
}
count++;
}
return -1;
}
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) {
if (pos < 0 || pos >= this.useSize) {
System.out.println("pos不合法!");
return;
}
for (int i = 0; i < this.useSize; i++) {
if (i == pos) {
this.elem[i] = value;
}
}
}
//删除第一次出现的关键字key
public void remove(int toRemove) {
int pos = search(toRemove);
if (pos == -1) {
System.out.println("无toRemove");
return;
}
for (int i = pos; i < this.useSize-1; i++) {
this.elem[i] = this.elem[i+1];
}
this.useSize--;
}
// 获取顺序表长度
public int size() {
int count = 0;
for (int i = 0; i < this.useSize; i++) {
count++;
}
return count;
}
// 清空顺序表
public void clear() {
this.useSize = 0;
}
}

链表种类:



单向、双向
带头、不带头
循环、非循环
经过排列组合,共8种
下面只讲单向、带头、非循环链表
单链表及相关接口实现



package TestDome;


class Node {
public int val;
public Node next;
public Node() {
}
public Node(int val) {
this.val = val;
}
}
public class MyLinkedList {
public Node head;
public void CreatedList() {
this.head = new Node(12);
Node node2 = new Node(22);
Node node3 = new Node(32);
Node node4 = new Node(42);
this.head.next = node2;
node2.next = node3;
node3.next = node4;
}
//找到最后节点
public void FindLastNode() {
Node cur = this.head;
if (this.head == null) {
System.out.println("链表为空");
return;
}
while (cur.next != null) {
cur = cur.next;
}
System.out.println(cur.val);
}
//找到次后节点
public void FindNextLastNode() {
Node cur = this.head;
if (this.head == null) {
System.out.println("链表为空");
return;
}
if (this.head.next == null) {
System.out.println("链表无次后节点");
return;
}
while (cur.next != null) {
if (cur.next.next == null) {
System.out.println(cur.val);
}
cur = cur.next;
}
}
//链表打印
public void Display() {
Node cur = this.head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//判断key值是否存在于链表
public boolean FindKey(int key) {
Node cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void AddFirst(int date) {
Node node = new Node(date);
if (this.head == null) {
this.head = node;
}else {
node.next = this.head;
this.head = node;
}
}
//尾插法
public void AddLast(int date) {
Node node = new Node(date);
Node cur = this.head;
if (this.head == null) {
this.head = node;
return;
}
while(cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
//链表长度
public int Size() {
int count = 0;
Node cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//找到AddIndex中date的前驱
public Node FindIndex(int index) {
Node cur = this.head;
int count = 0;
while (cur.next != null) {
if (count == index-1) {
return cur;
}
count++;
cur = cur.next;
}
return null;
}
//任意位置的插入
public void AddIndex(int index,int date) {
Node node = new Node(date);
if (index <= 0 || index > Size()) {
System.out.println("index不合法");
return;
}
Node cur = FindIndex(index);
if (cur == null) {
return;
}else {
node.next = cur.next;
cur.next = node;
}
}
//删除第一次出现key值的节点
public void Remove(int key) {
Node cur = this.head;
if (this.head == null) {
return;
}
while (cur.next != null) {
if (cur.next.val == key) {
cur.next = cur.next.next;
return;
}
cur = cur.next;
}
if (this.head.val == key) {
this.head = this.head.next;
}
}
//删除所有key值的节点
public void RemoveAll(int key) {
Node cur = this.head;
if (this.head == null) {
return;
}
Node del = this.head.next;
while (del != null) {
if (del.val == key) {
cur.next = del.next;
}else {
cur = del;
}
del = del.next;
}
if (this.head.val == key) {
this.head = this.head.next;
}
}
//反转链表
public void ReverseList() {
Node prev = null;
Node cur = this.head;
while (cur != null) {
Node curNext = cur.next;
if (cur.next == null) {
this.head = cur;
}
cur.next = prev;
prev = cur;
cur = curNext;
}
}
//找到中间节点
public Node MiddleNode() {
Node fast = this.head;
Node slow = this.head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
System.out.println(slow.val);
return slow;
}
}


相关推荐

最新更新

猜你喜欢